What is a useful skill hierarchy for an autonomous agent? We propose an answer based on a graphical representation of how the interaction between an agent and its environment may unfold. Our approach uses modularity maximisation as a central organising principle to expose the structure of the interaction graph at multiple levels of abstraction. The result is a collection of skills that operate at varying time scales, organised into a hierarchy, where skills that operate over longer time scales are composed of skills that operate over shorter time scales. The entire skill hierarchy is generated automatically, with no human intervention, including the skills themselves (their behaviour, when they can be called, and when they terminate) as well as the hierarchical dependency structure between them. In a wide range of environments, this approach generates skill hierarchies that are intuitively appealing and that considerably improve the learning performance of the agent.
Paper
Similar papers
Peer review
Summary
The paper proposes a method to discover skill hierarchy by applying hierarchical graph clustering methods to expose the structure. The proposed method introduces Louvain method for skill hierarchy revealing and produces skill hierarchy with multiple-grained of action abstractions. The proposed method is tested on six different environments and compared with other methods.
Strengths
This paper introduces the concept of graph clustering to discover action hierarchies, which is an interesting idea. The references are described in details, which makes the intuition and technique of the proposed method more reasonable. It is appreciated also the experiments in six different problems and the evaluation with other methods, as well as the ablation study.
Weaknesses
There are several weaknesses. First, this paper is poorly written. There are a lot of grammatical errors and unprofessional writing styles, which makes it difficult to understand. Technical writing in Proposed Approach part in this paper is also limited, causing a great deal of confusion about its proposed method. This paper attempts to solve the problem of action hierarchy discovery of agents. This problem is extremely difficult and could not be well solved by introducing Louvain-based graph clustering methods as described in the paper. More details will be described in the limitations. Moreover, the proposed approach section in the paper spends plenty of words to describe the process of the Louvain algorithm. However, the Louvain algorithm has been proposed in 2008 and there have been a lot of improved works during 2010-2015, which should not be the focus of the paper. In addition, although there are many tasks in the experiment section, these problems are all simple and some of them can be solved well even using simple planning methods. It is unnecessary to discover action hierarchies in these scenarios. Agents’ skills should be learned in more complex scenarios with more constraints, such as StarCraft II and the Minecraft (the recently popular environment), but these complex scenarios are not considered in this paper.
Questions
How about the learning efficiency of the proposed algorithm? Does the size of the graph limit the learning efficiency of the proposed method compared to the original reinforcement learning algorithm? I am confused that there is no diversity in the skills formed by combining only 4 actions with same type in these simple scenarios including Rooms. Poor diversity limited the performance of policies learned from the reinforcement learning framework. There are too many confusing descriptions, including: • "an autonomous agent" in Line1 • "graphical structure" in Line2 • "its environment" in Line2 • "multiple levels of abstraction" in Line4 • "regions of the state" in Line5 • "connected within themselves" in Line6 • "various levels of granularity" in Line16 • "outcome" in Line17 • "characterisation" in Line19 • "existing approaches to skill discovery" in Line55 • "are not without their limitations" in Line72
Rating
2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
1 poor
Presentation
2 fair
Contribution
1 poor
Limitations
Existing reinforcement learning algorithms based on the state-action space have achieved great results, especially in simple scenarios, which can achieve efficient exploration in the policy space. The reason for introducing skills to split the primitive action space into multiple parts for separate exploration is that the state action search space is so large in facing with more complex scenarios that the primitive reinforcement learning algorithm is inefficient for exploration. However, it is difficult for the skill-based approach to converge to the global optimal solution. The possibility of convergence to a local optimal solution in each subspace is high, which is more likely to occur in simple scenarios. This paper does not propose a theoretical guarantee on the learning efficiency of the algorithm and lacks the optimization analysis of the algorithm. In addition, it does not conduct experimental evaluation on complex scenarios to answer aforementioned questions. Louvain is a commonly used in community discovery to mine graph clusters. However, the learning process of Louvain algorithm and the learning process of reinforcement learning framework are independent. How can the clustering information of state action space mined by Louvain algorithm actively guide the reinforcement learning? How can the policy search process in the state-action space be fed back to the mining process of Louvain? I think it is difficult. In addition, the modularity seems to be independent of the reward in reinforcement learning, which may lead to the inability of combining the Louvain algorithm with the reinforcement learning algorithm, no matter what approach is taken. I wonder if graph partitioning can really guide skill learning. First concerning about the model-based reinforcement learning, which generates a complete state action transition graph. However, once the transition graph is completely knowable, traditional reinforcement learning methods can achieve great performance. There is no need to develop reinforcement learning method based on graph partitioning. In case of model-free reinforcement learning, where the policy learning of traditional reinforcement learning methods is difficult, graph partitioning will play a positive role. However, if the transition graph is unknown, it is impossible to reveal expective clusters of the transition graph. Therefore, the proposed method in this paper would be ineffective. But I think that combining graph partitioning method with model-free reinforcement learning with incomplete transition graph is a promising direction.
Summary
The paper proposes a graph-partitioning-based method to automatically learn multi-level hierarchies of skills at varying timescales in reinforcement learning. The method assumes existence of a complete state transition graph and applies Louvian algorithm to create a hierarchy of state clusters. By merging states, the algorithm creates state partitions that maximize modularity, which measures the quality of partitions based on strong connections within clusters and weak connections between them. The work considers an important unsolved problem of automatically creating multi-level skill hierarchies. The paper is written well, however, it needs more clarity. Some details regarding the assumptions made and the scope of problems need to be clarified right from the beginning to improve quality. The empirical evaluation could be improved by diversifying the choice of the domains because four out of six domains are extremely similar navigation domains, and clearly justifying the choice of baselines and their input requirements.
Strengths
The number of levels in a hierarchy do not need to be predefined, unlike existing methods. The proposed method automatically finds the levels in the hierarchy using no gain in modularity as a stopping condition.
Weaknesses
(I) The proposed method relies on concrete state transition graph and then uses hierarchal clustering based algorithm to iteratively merge states and produce a hierarchy of clusters. Hence, the method might not scale well to problems with large state space as the memory requirement would increase exponentially and learning a complete state transition graph would require exploration of the complete state space/high number of samples. (II) The assumption regarding the availability of a complete state space graph and the scope of the problems (discrete state space, low-dimensional, etc.) the method can handle need to be stated clearly. (III) The empirical evaluation could be improved by diversifying the selection of domains. It is unclear how the approach would perform in more complex decision-making tasks. (IV) An analysis of comparison of the number of samples required by each baseline to learn a hierarchy and option policies is needed. Minor: (I) line 20: has -> have (II) line 112: the partition -> the partition c_i is
Questions
(I) Can you explain "we use each of the h partitions to define a single layer of skills, resulting in a hierarchy of h levels.."? It is not clear how total number of partitions is directly affecting the number of the layers. (II) How can state abstraction be employed using the proposed method? (III) Can the current method handle continuous state space problems? (IV) How does the proposed work relate to [1]? (V) In empirical evaluation, how is the office world (without any objects) different from the maze world domain? (VI) Can you comment about scalability of the approach to handle domains with large state spaces? (VII) Do the baselines assume a state transition graph or start learning from scratch? Does the learning performance in Fig 3 include the samples required to learn the hierarchies? If not, how many samples were required to learn the hierarchies by different methods along with the samples required to learn the option policies? References: [1] Fox, R., Krishnan, S., Stoica, I. and Goldberg, K., 2017. Multi-level discovery of deep options. arXiv preprint arXiv:1703.08294.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
(Included in summary, weaknesses)
Summary
Given a graph of connectivity of the state space of an environment, this paper proposes to use a hierarchical clustering technique, the Louvain algorithm, to provide reinforcement learning with a multi-level skill representation. This allows policies to take actions at variable time scales, and experimental results show that the identified clusters allow faster learning in the domains studied.
Strengths
- Clarity of presentation. The graph clustering algorithm is motivated and described very clearly. The experiments are also well described. The visualizations of the hierarchical results are informative and easy to interpret. - Comparison with baselines. The paper describes five alternative graph-based approaches, and shows superior performance of the Louvain-based method. - Initial explorations into some limitations. The paper points out that the method requires full knowledge of the state space and it's graph representation. Initial results explore what happens when the clustering is learned online with interaction in the environment. The paper also explores extending the method to continuous state spaces. - Thorough discussion section.
Weaknesses
- Although the description of the Louvain algorithm and most of the rest of the paper is quite thorough and well presented, the method for training a policy using the hierarchical clustering output is left comparatively sparse. Especially since the cited method may not be readily familiar to a modern audience.
Questions
The paper is very clear. Other than the weakness mentioned above, I do not feel I have pressing questions.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Limitations are more than adequately addressed, as mentioned in the strengths section above.
Summary
This paper addresses the problem of discovering a hierarchy of skills based on the state-transition graph. The proposed approach builds on an existing method called the Louvain algorithm, which creates a hierarchy of state clusters; i.e., the lowest level will place nearby states in the same (small) cluster, the second level will place those smaller clusters in bigger clusters, and so on. The clusters are defined using a measure of modularity (nodes within a cluster have dense connections, but there are sparse connections between different clusters). The skills are then defined using the options framework, and their behavior is to take the agent from any state within the cluster to the adjacent clusters. The empirical evaluation presented indicates that the method is capable of finding such hierarchies of skills and that, in some cases, using these skills yields a better performance when learning to solve a task, when compared with existing methods. Additionally, the empirical evaluation demonstrates the method's efficacy under scenarios with continuous state spaces (assuming a discretization method) and under scenarios with many states. Finally, the authors present preliminary results for a possible extension of the method to an interactive case where the transition graph is also learned dynamically instead of being assumed available originally.
Strengths
- The paper addresses a very interesting, novel, and important problem: to autonomously identify a hierarchy of skills with multiple levels (not only two as in most previous work), without specifically setting the number of levels it should have. - The proposed method is intuitive and has a different/creative look at a problem that has not been solved yet. The paper is very clearly written, with a very good display of the empirical results, analyzing both qualitative and quantitative aspects of the learned skills. - The experiments conducted indicate that the hierarchies learned are presenting the desired behavior (i.e., clusters well connected within themselves but not well connected between each other). - The domains used in the empirical evaluation cover a wide range of scenarios: smaller, simpler MDPs, but also MDPs with many states and even an MDP with discretized continuous states. This helps demonstrate the effectiveness of the method at different levels of complexity.
Weaknesses
- The method requires complete knowledge of the state-transition graph, which is often not available in real-life applications. However, I believe the paper still presents an important contribution and a first step towards solving the problem of finding multi-level hierarchies of skills. Additionally, the authors present preliminary results for an incremental version of the algorithm, where the skills are adjusted as the estimated model is learned. - Without limiting the number of clusters/levels in some way, the algorithm could end up returning a lot of skills, which could make the learning process later on more difficult instead of facilitating it (given the increased action space). The authors mention this in the paper and propose one possible improvement (to ignore lower-level clusters that contain a small number of states). - The method finds skills using only the transition graph, not the reward function. Thus, it would not be as useful in tasks with a large state space but where only a small subset of it is used for solving the task.
Questions
- Why did the authors select Q-learning as the baseline for primitive actions instead of a more recent, and better-performing, algorithm? - It seems like the first two plots of Figure 4 do not present the results for Level 4. Could the authors please clarify this? - Currently, as per my understanding, all edges in the graph have the same weight. This would imply that when finding the skills in non-deterministic MDPs, a transition that happens with a 10% probability would have the same importance as one that always happens. Do the authors have an insight into how the algorithm could be changed to consider the transition probabilities?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
The authors discuss the limitations of the work. No major concerns.
Thank you for your response, I agree that the exact method of training the options is not a main point of the paper. Thanks for pointing out where the set-up was described nonetheless.
Thank you for the comments. But I am keeping my original score given the limitations of your work: 1. The paper claims that the main contribution is a characterisation of a useful action hierarchy which is an action structure. The action structure is intuitive and easily constructed. Many works have made efforts in this aspect [1-7]. The action structure can even be represented as a graph structure, and many works have done so [8-10]. Therefore, it should not be considered as a contribution of the paper. The paper also claims that it uses Louvain-based graphical representation method for the characterisation of the action hierarchy. However, the Louvain algorithm has long been proposed with many improvement works[11-15]. Besides, as mentioned in the related work, many works have used graph partitioning methods for skill discovery[16-19]. Therefore, the real contribution of this paper is only constructing the state-action space for option learning based on the graph partitioning results. However, the option learning method is not described either in this paper or in the supplementary material. From the description of the Analysis sector, it seems that this method is not different from the classical reinforcement learning methods. **In summary, what this paper does is merely using the Louvain method to generate clustering results of the transition graph for training classical RL algorithms, without substantial innovation.** 2. In the Introduction section of this paper, the author claims that proposed approach differs from existing methods in two ways: parition the interaction graph by maximising modularity and producing a multi-level hierarchy. However, the first difference has already been clearly proposed in the fast unfolding method[11]. Part of the second, which generates a hierarchical clustering structure has also been described in the fast unfolding method[11]. Therefore, the only real difference between this method and existing work isonly a very small part mentioned in the paper, which is constructing the state-action space for option learning based on the clustering results. In fact, the proposed method does not have much novelty compared to classical reinforcement learning methods. **Therefore, there is so little original content in this paper that it would not be accepted in a top-tier conference**. 3. The author notes that there is no basis for this statement that skill discovery cannot be solved by introducing Louvain-based graph clustering methods and skill discovery is an open problem and Louvain-based graph clustering methods may well be part of the solution. **I wonder to know if there's any basis for the author's claim?** The open problem cannot be solved by mere textual description. We consider two commonly used methods. - The first is the theoretical analysis. Is there any theoretical analysis in this paper? **Neither the main content nor the supplementary material contains the theoretical analysis of the proposed approach.** - The second is experiments. Although the paper describes several experimental scenarios, these scenarios are all too simple. These scenarios were usually used in papers published 20 years ago, but recent work has rarely used such simple scenarios for experiments, except for papers about the theoretical analysis of reinforcement learning. Recent work has typically used scenarios such as Atari and Mujoco for experiments. As stated in the previous part, there is no theoretical analysis in this paper, so it should be evaluated on Atari or Mujoco or even more complex scenarios such as MineCraft or SMAC to be convincing. **Even author noted in Line 57 in the paper that multi-level skill hierarchies are essential for solving complex tasks. Why are there no experiments on such complex scenarios? In my opinion this paper won't be accepted in a top-tier conference while you don't have a non-toy problem evaluation.** 4. Some issues. - If options are used to solve complex problems, then they should be diverse. In this case, the proposed approach that options control agents move between adjacent state spaces does not make sense, because such options cannot adapt to scenarios that require options to extensively explore different action spaces. - The proproposed approach is built on the assumption that the Louvain method successfully generates good clustering results. If the Louvain method fails or generates clustering results with low quality, the proproposed approach will fail. Such situations are prevalent in the experimental scenarios commonly used in current works. The state-action features of these scenarios do not have characteristics conducive to unsupervised clustering, and cannot generate appropriate clustering results by simply applying the Louvain method. - If the collected transition graph is only a small part of that in the entire senario, then the results do not provide meaningful guidance for solving the entire problem.
- The proposed approach combing lower actions into higher level may not be efficient. It may be less efficient than directly learning actions. [1] Şimşek, Özgür, and Andrew Barto. "Skill characterization based on betweenness." Advances in neural information processing systems 21 (2008). [2] Konidaris, George, and Andrew Barto. "Skill discovery in continuous reinforcement learning domains using skill chaining." Advances in neural information processing systems 22 (2009). [3] Vigorito, Christopher M., and Andrew G. Barto. "Intrinsically motivated hierarchical skill learning in structured environments." IEEE Transactions on Autonomous Mental Development 2.2 (2010): 132-143. [4] Hengst, Bernhard. "Discovering hierarchy in reinforcement learning with HEXQ." ICML. Vol. 19. 2002. [5] Thrun, Sebastian, and Anton Schwartz. "Finding structure in reinforcement learning." Advances in neural information processing systems 7 (1994). [6] Mugan, Jonathan, and Benjamin Kuipers. "Autonomously learning an action hierarchy using a learned qualitative state representation." (2009). [7] Konidaris, George Dimitri, and Andrew G. Barto. "Efficient Skill Learning using Abstraction Selection." IJCAI. Vol. 9. 2009. [8] Firby, R. James, and Marc G. Slack. "Task execution: Interfacing to reactive skill networks." AAAI Spring Symposium. 1995. [9] Bagaria, Akhil, Jason K. Senthil, and George Konidaris. "Skill discovery for exploration and planning using deep skill graphs." International Conference on Machine Learning. PMLR, 2021. [10] do Couto, Jorge Manuel Ferreira. "Learning from Demonstration using Hierarchical Reinforcement Learning for Robotic Skill transferability." (2022). [11] Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008. [12] De Meo, Pasquale, et al. "Generalized louvain method for community detection in large networks." 2011 11th international conference on intelligent systems design and applications. IEEE, 2011. [13] Traag, Vincent A. "Faster unfolding of communities: Speeding up the Louvain algorithm." Physical Review E 92.3 (2015): 032801. [14] Dugué, Nicolas, and Anthony Perez. Directed Louvain: maximizing modularity in directed networks. Diss. Université d'Orléans, 2015. [15] Bhowmick, Ayan Kumar, et al. "Louvainne: Hierarchical louvain method for high quality and scalable network embedding." Proceedings of the 13th international conference on web search and data mining. 2020. [16] Moradi, Parham, Mohammad Ebrahim Shiri, and Negin Entezari. "Automatic skill acquisition in reinforcement learning agents using connection bridge centrality." Communication and Networking: International Conference, FGCN 2010, Held as Part of the Future Generation Information Technology Conference, FGIT 2010, Jeju Island, Korea, December 13-15, 2010. Proceedings, Part II. Springer Berlin Heidelberg, 2010. [17] Rad, Ali Ajdari, Martin Hasler, and Parham Moradi. "Automatic skill acquisition in Reinforcement Learning using connection graph stability centrality." Proceedings of 2010 IEEE International Symposium on Circuits and Systems. IEEE, 2010. [18] Şimşek, Özgür, Alicia P. Wolfe, and Andrew G. Barto. "Identifying useful subgoals in reinforcement learning by local graph partitioning." Proceedings of the 22nd international conference on Machine learning. 2005. [19] Kazemitabar, Seyed Jalal, and Hamid Beigy. "Using strongly connected components as a basis for autonomous skill acquisition in reinforcement learning." Advances in Neural Networks–ISNN 2009: 6th International Symposium on Neural Networks, ISNN 2009 Wuhan, China, May 26-29, 2009 Proceedings, Part I 6. Springer Berlin Heidelberg, 2009.
Response to Points 1 and 2
We thank the reviewer for their continuing engagement with the paper. Below we provide a point-by-point response to the concerns raised. We believe that we have addressed all of the main concerns. (1) The innovation in the paper is the use of an existing method (Louvain Algorithm) in a new context (temporal abstraction in reinforcement learning). **This is an established and valuable form of contribution to science.** Our use of the Louvain Algorithm brings something new and useful to temporal abstraction in reinforcement learning, achieving something that is not yet possible with ANY existing approach: autonomous specification of a multi-level action hierarchy with no human input. Organising the state-action space of an agent into a skill hierarchy is no easy task. Louvain skills do it elegantly and successfully. This is an important result for the field. Please note the following: (a) Yes, some existing characterisations of skill hierarchies use the state-transition graph, and some of these methods use graph partitioning; we note this clearly in the paper. There is a fundamental limitation shared by all existing graph-based methods: they lead to skill hierarchies with only **a single level** above primitive actions. The necessity of **multi-level** abstraction is clear; it is noted frequently in the literature (e.g.; Barto, Singh, Chentanez, ICDL 2004; Singh, Barto, & Chentanez, NeurIPS 2004). (b) The reviewer wrote: *“However, the Louvain algorithm has long been proposed with many improvement works[11-15]”*. This is a point that the reviewer raised earlier; we have already responded to it: These later works are not relevant in the context of temporal abstraction in reinforcement learning. If the reviewer knows differently, we would welcome the new information, but the reviewer needs to explain which particular later development is useful in our context and why. It is also worth noting that any existing/future improvements to the Louvain algorithm, where relevant and useful, can be **directly** incorporated into our approach as long as the output of the algorithm is a cluster hierarchy. In short, we argue that this objection is not valid. We note that it is not possible to further respond to it without further details from the reviewer. (c) The method used to train option policies is detailed in the Supplementary Material (Appendix F), and also in our discussion with Reviewer 4HvS. This is just one example of how Louvain option policies can be trained; other approaches exist. Our analysis focused on how useful the Louvain options are when they are available to an agent; therefore, precisely how the option policies were trained did not matter as long as the learned policies were accurate. (d) Factual correction: Cited works [16] and [17] are not based on graph partitioning, as claimed by the reviewer. They use graph centrality measures to find bottleneck states and produce skills that efficiently take the agent to these states. --- (2) We do not claim to contribute a novel hierarchical graph partitioning algorithm. On the contrary, we clearly state throughout the paper that we use the Louvain algorithm (Blondel et al., 2008) to perform hierarchical graph partitioning. Please see our response to point 1 above for the innovation in the paper.
Response to Point 3
(3) We argue that the entire paper supports our claim, including the following results: (i) In a wide variety of domains, Louvain skills form a multi-level hierarchy that matches human intuition well (Figure 2). (ii) Agents using Louvain skills consistently learn faster than agents using only primitive actions and agents using skills produced by existing approaches (Figure 3). (iii) Agents learn more quickly when Louvain skills are arranged into a multi-level hierarchy compared to when each skill calls primitive actions directly (Figure 4). (iv) Agents learn more quickly with the full Louvain hierarchy compared to when each level of the skill hierarchy is used in isolation (Figure 4). (v) The proposed approach continues to produce good skill hierarchies in environments with over 1 million states (Figure 5b). The Louvain agent continues to have a clear and substantial advantage over other approaches in the largest domain we tested (Figure 5c). (vi) We explore two possible paths towards discovering Louvain skills incrementally, while an agent is interacting with its environment, with positive results (Figure 6). (vii) We illustrate how a Louvain cluster hierarchy can be produced in a problem with a continuous state space (Figure 7). ***On theoretical results:*** (1) Louvain skills have a solid basis in graph theory. (2) We have already noted in our earlier response that any existing convergence results in reinforcement learning continue to hold because learning continues in primitive-action space. This is well known so we did not see the need to include it in the paper. We can do so if the reviewer believes it to be useful. (3) The reviewer is asking for theoretical results but without specifying what they should/could be. Can the reviewer be more specific? Precisely what type of theoretical analysis would be applicable, feasible, and useful? ***Scenarios used in the experiments:*** First, we note that it is entirely irrelevant how old the scenarios are; what matters is how useful they are in answering scientific questions posed in the paper. Therefore, “age” is not a valid scientific objection to the scenarios used. Secondly, the reviewer’s comment misses the following: **In these scenarios, our approach achieves something that is not achieved by ANY existing approach: autonomous specification of a multi-level action hierarchy with no human input.** Furthermore, empirical results are presented on a diverse set of scenarios, and they consistently show positive results for the proposed approach. Thirdly, something that is a key difficulty for the field as a whole — scaling up graph-based skill discovery algorithms to very large domains — cannot be the basis of rejecting a new paper that brings forward a new idea whose utility, as well as comparative strengths to existing methods, is clearly demonstrated in smaller domains. We expand on this third point below. Constructing graphical representations for very large environments – such as those with continuous (e.g., MuJoCo) or high-dimensional (e.g., Atari and SMAC) state spaces – is a key open problem. Addressing this problem is not our focus. We are asking a more fundamental question: What is a useful skill hierarchy? Scaling up is a different question; and, importantly, it is an **orthogonal** question: Any promising future graph construction method for such domains can be **immediately** incorporated into the proposed approach to produce Louvain skills. It is also noteworthy that any solution to the scaling-up question will benefit not only our approach but basically all other graph-based approaches to skill discovery (as well as other areas of reinforcement learning). Scientific progress is achieved by divide-and-conquer; not all questions can or should be addressed in one conference paper.
Response to Points 4.1, 4.2, and 4.3
*(4) Some issues.* *(4.1) If options are used to solve complex problems, then they should be diverse. In this case, the proposed approach that options control agents move between adjacent state spaces does not make sense, because such options cannot adapt to scenarios that require options to extensively explore different action spaces.* It is not clear what the reviewer means by *“diverse”*. As noted in our earlier response, Louvain skills are diverse in their initiation sets, policies, termination conditions, and temporal reach. They provide good coverage of the entire state space. It is unclear what other source of diversity one could want from a given class of skills. We also do not understand what the reviewer means by *“scenarios that require options to extensively explore different action spaces”*. In particular, what does the reviewer mean by *“different action spaces”*? Can they please express it in the mathematical notation used in the paper? e.g., $A(s)$ is the set of actions available from state $s$ in a given MDP. What exactly are the *“different action spaces”* the reviewer refers to? In short, it is not possible to respond to a concern that is not clearly stated. Can the reviewer please further explain their concern? It would help us understand the concern if they are able to point to any existing approach to skill discovery that addresses this concern. --- *(4.2) [...] If the Louvain method fails or generates clustering results with low quality, the proposed approach will fail. Such situations are prevalent in the experimental scenarios commonly used in current works. The state-action features of these scenarios do not have characteristics conducive to unsupervised clustering, and cannot generate appropriate clustering results by simply applying the Louvain method.* (i) The reviewer wrote *“Such situations are prevalent in the experimental scenarios commonly used in current works.”* How prevalent? What are these works? Can the reviewer please provide references so that we can look at the evidence? On the contrary, existing work suggests that, if there exists modular structure in a given network, the Louvain algorithm usually identifies it (e.g., see Lancichinetti & Fortunato, 2009). This is also what we found in our experiments, as reported in the paper. (ii) It is possible, even likely, that no single skill characterisation will work perfectly in all possible scenarios. This is not a problem. An agent is not limited to using a single approach to skill discovery; it can (and probably should) use multiple different approaches. It is useful to know what type of environments each discovery algorithm is well suited to. Some problems will have strong modular structure, and others may not; Louvain skills will be better-suited to the former cases than the latter. (iii) Even in the absence of modular structure, we still observed that the proposed approach produced useful and intuitively-appealing skills. For instance, consider the Level 2 skills produced in Rooms (Figure 2, top row, third column). The skills for moving between the clusters within each room clearly enable efficient low-level navigation of the state space, despite the fact that the internal structure of each room is uniform. --- *(4.3) If the collected transition graph is only a small part of that in the entire scenario, then the results do not provide meaningful guidance for solving the entire problem.* (i) As soon as any state is visited the very first time, it can be added to the state-transition graph. If unknown parts of the state-transition graph are relevant for solving the problem, the agent will visit those states sooner or later. (ii) Future work can explore how to generalise graph structure from known parts of the state space to unknown parts of the state space. This is an orthogonal research question that can be explored in isolation from the current paper and would benefit many areas of reinforcement learning beyond skill discovery.
Response to Point 4.4
*(4.4) The proposed approach combing lower actions into higher level may not be efficient. It may be less efficient than directly learning actions.* We find this claim surprising and counter-intuitive. We would welcome any reasoning and evidence that the reviewer can provide to support their claim. We argue the opposite, with clear reasoning and evidence: Building multi-level skill hierarchies leads generally to increased learning efficiency. When an agent executes a skill, it learns (through reinforcement learning algorithms) about the consequences of executing not only that skill but also ALL lower-level skills (and, ultimately, primitive actions) that the skill calls upon when executing. So multi-level skills introduce a clear learning efficiency in this way. This is supported by the results in our paper: agents with Louvain skills arranged as a multi-level hierarchy – where lower-level skills are composed into higher-level skills – consistently learned more efficiently than agents using “flat” Louvain skills which call primitive actions directly (Figure 4). Furthermore, when learning option policies, it is more economical to form new higher-level skills by composing already-trained lower-level skills than it is to start training from scratch using only primitive actions. As a simple example, if an agent already knows how to leave the room, it can use this knowledge (i.e., skill) when learning how to leave the building. --- Once again, we thank the reviewer for their continued attention to the paper and hope that our comments are useful in evaluating the paper.
Thank you for your thorough response. After reading it, and the other reviews and discussion, I tend to maintain my original score. I agree that there are limitations and that the idea might be seen as simple, but the limitations are discussed in the paper and I believe this is a valuable contribution to the field.
Decision
Accept (poster)