Creating Multi-Level Skill Hierarchies in Reinforcement Learning
Authors: Joshua Benjamin Evans
Özgür Şimşek
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Hierarchical Reinforcement Learning
RL
HRL
Skill Discovery
Skill Hierarchies
Graph-Based
Graphs
Graph Clustering
Graph Partitioning
TL;DR: We propose a novel graph-based characterisation of a useful multi-level skill hierarchy for reinforcement learning.

Abstract: 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 input, including the skills themselves (their behaviour, when they can be called, and when they terminate) as well as the 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.

Creating Multi-Level Skill Hierarchies in Reinforcement Learning
Joshua B. Evans
Özgür Şimşek
Department of Computer Science
Department of Computer Science
University of Bath Bath, United Kingdom jbe25@bath.. ac. uk
University of Bath Bath, United Kingdom o. s wissseebaathh...mmm........m...e ac uk
Abstract
What is useful skill hierarchy for an autonomous agent? We propose an answer based graphical representation of how the interaction between agent and its environment may unfold. Our approach uses modularity maximisation as a central organising principle expose the structure of the interaction graph multiple levels of abstraction. The result is collection of skills that operate at varying time scales, organised into hierarchy, where skills that operate longer time scales are composed of skills that operate over shorter time scales. The entire skill hierarchy generated automatically, with no human intervention, including the skills themselves (their behaviour, when they can be called, and when they terminate) as well the hierarchical dependency structure between them. wide range of environments, this approach generates skill hierarchies that are intuitively appealing and that considerably improve the learning performance of the agent.
Introduction
One of the most important open problems in artificial intelligence is how to make it possible for autonomous agents to develop useful action hierarchies on their own, without any input from humans, including system designers and domain specialists. Before addressing this algorithmic question, is useful to first consider a conceptual one: What constitutes a useful action hierarchy? Here we focus on this conceptual question with the aim providing useful foundation for algorithmic development.
Our primary contribution characterisation of a useful action hierarchy. In defining this action hierarchy, we use no information other than a graphical representation of how the interaction between the agent and its environment may unfold. When this information is not known priori, it would be discovered naturally by the agent as it operates in its environment. Beyond this interaction graph, no particular domain knowledge is needed. Hence, our approach applicable broadly.
Multiple strands of earlier work have used the interaction graph as a basis for defining collections of actions. The main novelty in approach is organising principle to expose the structure of the interaction graph at multiple levels of abstraction. The outcome an action hierarchy that enables the agent to explore its environment efficiently at multiple time scales.
of modularity maximisation
central
Our approach yields an action hierarchy with four desirable properties. First, it contains actions that operate at a wide range of time scales. This is necessary to solve complex problems, which require agents to be able act, learn, and plan at varying time scales. Secondly, the actions naturally organised into a hierarchy, with actions that operate over longer time scales being composed of actions that operate over shorter time scales. This hierarchical structure offers substantial benefits
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

over unstructured collections of actions. For example, it allows an agent to learn about not only the action it is currently executing but also all lower-level actions that are called in the process. In addition, a hierarchical structure allows actions to be updated in modular fashion. For instance, any improvements to an action would be immediately reflected in all higher-level actions that call it. Thirdly, the action hierarchy is fully specified. This includes when each action can be selected for execution, how exactly it behaves, and when it terminates. It also includes the number of levels in the hierarchy and the exact dependency structure between the actions. Fourthly, the action hierarchy is generated automatically, with no human intervention.
In a diverse set of environments, the proposed approach translates into action hierarchies that are intuitively appealing. When evaluated within the context of reinforcement learning, they substantially improve learning performance compared to alternative approaches, with the largest performance improvement observed in the largest environment tested.
An important question for future research is how such an action hierarchy may be learned when the agent has no prior knowledge of the dynamics of the environment. We present an initial exploration of how this may be achieved, with positive results.
2 Background
We use the reinforcement learning framework, modelling agent's interaction with its environment as a finite Markov Decision Process (MDP). An MDP is a six-tuple (S, P, R, D),,, where S is finite set of states, A is finite set of actions, P S x A x S > [o, 1] is a transition function, R S x A x + R is a reward function, D : - [o, 1] is an initial state distribution, and y E [o. 1] is discount factor. Let A(s) denote the set of actions available in state S. At decision stage t, t 2 O, the agent observes state 8, E S and executes action a E A(s)). Consequently, at decision stage L 1, the agent receives reward rt+1 R and observes new state 81+1 S. The return at decision stage i, denoted by G., is the discounted sum of future rewards, G. = 3000
=k== 7 + A policy 8 x A - [0, 1] specifies the probability of selecting action A in state 8 E S. The objective is to learn a policy that maximises the expected return.
The state transition graph of an MDP is a weighted, directed graph whose nodes correspond to the states of the MDP and whose edges correspond to possible transitions between states. Specifically, an edge (u, v) exists on the graph if it is possible to transition from state E S to state S by taking some action a E A(u). In this paper, we use uniform edge weights of 1.
The actions of an MDP take exactly one decision stage to execute. We refer to them as primitive actions. Using primitive actions, it possible to define abstract actions, also known as skills, whose execution can take a variable number of decision stages. Furthermore, primitive and abstract actions can be combined to form complex action hierarchics. In this work, we represent abstract actions using the options framework [1, 2]. An option o is three-tuple (Io, To, 3.),, where I, C S is the initiation set, specifying the set of states in which the option can start execution, To : A - [0. 1] is the option policy, and 3. S + [0, 1] is the termination condition, specifying the probability of option termination in a given state. An option policy is ultimately defined in terms of primitive actions because primitive actions environment- but this can be done indirectly by allowing options to call other options, making possible for agents act, lear, and plan with hierarchies of primitive and abstract actions.
the fundamental units of interaction between the agent and its
3 Proposed Approach
To define a skill hierarehy, we use modularity maximisation as a central organising principle, applied at multiple time scales. Specifically, we represent the possibilities of interaction between the agent and its environment as a graph and identify partitions of this graph that maximise modularity [3-5].
A partition of a graph is a division of its nodes into mutually exclusive groups, called clusters. The modularity of partition composed of a set of clusters C (2,,02, Ce,..,,...... , 3 is
pa,
1=1
2

---

where eū denotes the proportion of total edge weight in the graph that connects two nodes in cluster C, and a, denotes the proportion of total edge weight in the graph with at least one end connected to node in cluster c;. A resolution parameter / > 0 controls the relative importance of ea and o;. Intra-cluster edges contribute to both eqz and a; while inter-cluster edges contribute only to a;- A partition that maximises modularity will have relatively dense connections within its clusters and relatively sparse connections between its clusters.
Finding partition that maximises modularity for given graph is NP-complete [6]. Therefore, when working with large graphs. approximation algorithms are needed. The most widely used approximation algorithm is the Louvain algorithm [7], which is an agglomerative hierarchical graph clustering approach. While no formal analysis exists, the runtime of the Louvain algorithm has been observed empirically to be linear in the number of graph edges [8]. It has been successfully applied to graphs with millions of nodes and billions of edges [7].
An important feature of the Louvain algorithm is that, as a hierarchical graph clustering method, exposes the structure of a graph at multiple levels of granularity. Specifically, the output of the Louvain algorithm is a sequence of partitions of the input graph. This sequence has a useful structure: multiple clusters found in one partition in the sequence are merged into a single cluster in the next partition in the sequence. In other words, the output is a hierarchy of clusters, with earlier partitions containing many smaller clusters that are merged into fewer larger clusters in later partitions. This hierarchical structure forms the basis of our characterisation of a useful multi-level skill hierarchy.
The Louvain algorithm starts by placing each node of the graph in its own cluster. Nodes are then iteratively moved locally, from their current cluster to a neighbouring cluster, until no gain in modularity is possible. This results in revised partition corresponding to local maximum of modularity with respect to local node movement. The revised partition is used to define an aggregate graph as follows: each cluster in the partition is represented as single node in the aggregate graph, and directed edge is added to the aggregate graph if there is at least one edge that connects neighbouring clusters in the corresponding direction. This process is then repeated on the aggregate graph, and then on the next aggregate graph, and so on, until an iteration is reached with no modularity gain. Pseudocode for the Louvain algorithm presented in Section H of the supplementary material.
Let denote the number of partitions returned by the Louvain algorithm when applied to the state transition graph. We use each of the h partitions to define a single layer of skills, resulting in action hierarchy with h levels of abstract actions (skills) above primitive actions. Each level of the hierarchy contains one more skills for efficiently navigating between neighbouring clusters of the state transition graph. Specifically, we define an option for navigating from a cluster c, to a neighbouring cluster Cj as follows: the initiation set consists of all states in e;; the option policy efficiently takes the agent from a given state in e to a state in cy: the option terminates with probability 1 in states in Cy. with probability 0 otherwise.
Taking advantage of the natural hierarchical structure of the partitions produced by the Louvain algorithm, we compose the skills at one level of the hierarchy to define the skills at the next level up. That is, at each level of the hierarchy, option policies call actions (options or primitive actions) from the level below, with primitive actions being called directly by option policies from only the first level of the hierarchy. We call the resulting set of skills the Louvain skill hierarchy.
4 Related Work
There have been earlier approaches to skill discovery using the state transition graph. The approach we propose here differs from them in two fundamental ways. First, it is novel in its use of modularity maximisation as central organising principle for skill discovery. Secondly, it produces multi-level hierarchy, whereas existing graph-base based approaches produce hierarchies with only a single level of skills above primitive actions.
Many existing approaches to skill discovery use the state transition graph to identify useful subgoal states and define skills that efficiently take the agent to these subgoals. Suggestions for useful subgoals have often been inspired by the concept of a "bottleneck".. They include states that are on the border of strongly-connecte regions of the state space [9], states that allow transitions between different regions of the state space [10], and states that lie on the shortest path between many pairs of states [11]. To identify such states, several approaches use graph centrality measures [1 [11-15]. Others use graph
3

---

partitioning algorithms [9, 16-22], Alternatiely, it has been proposed that "landmark" states found the centre of strongly-commected regions of the state-space can be used subgoals [23].
The proposed approach is most directly related to skill discovery methods that make use of graph partitioning to identify meaningful regions of the state transition graph and define skills for navigating between them [16, 24-28j. Three of these methods use the concept of modularity. One such approach generate series of possible partitions by successively removing the edge with the highest edge betweenness from a graph, then selecting the partition with the highest modularity [25]. second approach to generate partition using the label propagation algorithm and then to merge neighbouring clusters until no gain in modularity is possible [28]. In these two approaches, modularity maximisation is applied after first producing candidate partitions using different criteria. Consequently, the final partition does not maximise modularity overall. The time complexity of the label propagation method near-linear in the number of graph edges, whereas the edge betweenness method has time complexity of O(m²n) on graph with edges and nodes. A third approach is by Xu al. [27]. who use the Louvain algorithm to find a partition that maximises modularity but, unlike our approach, define skills only for moving between clusters in the highest-level partition, discarding all lower-level partitions, All three methods produce single level skills above primitive actions.
Several approaches have used the graph Laplacian [29, 30] to identify skills that are specifically useful for efficiently exploring the state space. It is unclear how to arrange such skills to form multi-level skill hierarchies. contrast, the proposed approach produces a set of skills that are naturally arranged into a multi-level hierarchy.
While existing graph-based methods do not learn multi-level hierarchies, policy-gradies methods have made some progress towards this goal. Bacon et al. [31] extended policy-gradient theorems [32] allow the learning of option policies and termination conditions hierarchy with single level of skills above primitive actions. Riemer et al. [33] further generalised these theorems to support multi-level hierarchies. Fox al. [34] propose imitation learning method that finds the multi-level skill hierarchy most likely to generate given set of example trajectories. Levy et al. [35] propose method for learning multi-level hierarchies of goal-directed policies, with each level of the hierarchy producing a subgoal for the lower levels to navigate towards. However, these methods are not without their limitations. Unlike the approach proposed here, they all require the number of hierarchy levels to be pre-defined instead of finding a suitable number automatically. They do not jodicciois define initiation sets, instead making all skills available in all states. They also target different types of problems than we do, such as imitation-learning goal-directed problems.
Empirical Analysis
We analyse the Louvain skill hierarchy in the six environments depicted in Figure I: Rooms, Grid, Maze [23], Office, Taxi [36], and Towers of Hanoi. In all environments, the reward is -0.001 for each action and an additional +1.0 for reaching goal state. In Rooms, Grid, Maze, and Office, there are four primitive actions: north, south, east, and west. In Taxi, there are two additional primitive actions: pick-up-pasee passenger and put-down-passenn passenger. Some decisions in Taxi are irreversible. For instance, after picking up the passenger, the agent cannot return to a state where the passenger still waiting to be picked up. We describe each of these environments fully in Section A of the supplementary material.
When generating partitions of the state transition graph using the Louvain algorithm, we used resolution parameter p 0.05, unless stated otherwise. When converting the output of the Louvain
B
Rooms
Grid
Maze
Office
Taxi
Towers Hanoi
Figure 1: The environments.

---

algorithm into a concrete skill hierarchy, we discarded all levels of the cluster hierarchy where the mean number of nodes per cluster was less than 4. Our reasoning that skills that navigate between such small clusters execute for only a very small number of decision stages (often only one or two) and are not meaningfully more abstract than primitive actions. For all methods used in our comparisons, we generated options using the complete state transition graph and learned their policies offline using macro-Q learning [37]. We trained all hierarchical agents using macro-Q learning and intra-option learning [38]. Although these algorithms have not previously been applied to multi-level hierarchies, they both extend naturally to this case. The primitive agent was trained using Q-Learning [39]. The shaded regions on the learning curves represent the standard error in 40 independent runs. All experiments are fully described in Section B of the supplementary material.
Our analysis is directed by the following questions: What is the Louvain skill hierarchy generated in each environment? How does this skill hierarchy impact the learning performance of the agent? How do the results change as the number of states increases? Does arranging skills into a multi-level hierarchy provide benefits over a flat arrangement of the same skills? What is the impact of varying the value of the resolution parameter p?
Louvain Skill Hierarchy. We first examine the cluster hierarchies generated by applying the Louvain algorithm to the state transition graphs of various environments. Figure 2 shows the results in Rooms, Office, Taxi, and Towers of Hanoi. Section D of the supplementary material shows additional results in Grid and Maze.
In Rooms, the hierarchy has four levels. At level three, own cluster. Moving up the hierarchy, at level four, two of these rooms have been joined together into single cluster. Moving down the hierarchy, each room has been divided into smaller clusters level two, and then into even smaller clusters at level one. The figure illustrates how the corresponding skill hierarchy would enable efficient navigation between and within rooms.
that each room has been placed in its
In Office, at the top level, we see six large clusters connected by corridors. As we move lower down the hierarchy, see that these large clusters have been divided into increasingly smaller regions. At level three, there are many rooms that form their own cluster. At level two, most rooms have been divided into multiple clusters. The figure reveals how the corresponding skill hierarchy would enable efficient navigation of the environment at multiple time scales.
In Taxi, the state transition graph has four disconnected components, each corresponding to one particular passenger destination: R, G, B, or Y. In Figure 2, we show only one of these components, the one where the passenger destination is B. The results for the other components are similar. The Louvain cluster hierarchy has four levels. At the top level, we see four clusters. In three of these clusters, the passenger is waiting at their starting location (R, G, or Y). In the fourth cluster, the passenger is either in-taxi or has been delivered to their destination (B). Navigation between these clusters is unidirectional, with only three possibilities. The three corresponding skills navigate the taxi to the passenger location and pick up the passenger. Moving one level down the hierarchy, the clusters produce skills that move the taxi between the left and the night-hand side of the grid, which are connected by the bottleneck state at the centre of the taxi navigation grid.
In Towers of Hanoi, the hierarchy has three levels. At level three, moving between the three clusters corresponds to moving the largest disk to a different pole. Each of these clusters has been divided into three smaller clusters at level two and then into three even smaller clusters at level one. A similar structure exists at levels two and one. The smaller clusters at level two correspond to moving the second-large largest disc between different poles; the smallest clusters at level one correspond to moving the third largest disc between different poles.
In all of these domains, the Louvain skill hierarchy closely matches human intuition. In addition, it is clear how skills at one level of the hierarchy can be composed to produce the skills at the next level.
Learning Performance. We compare learning performance with the Louvain skill hierarchy to approaches based Edge Betweenness [25] and Label Propagation [28], as well as to the method proposed by Xu et al. [27]. These methods are the most directly related to the proposed approach, as discussed in Section 4. In addition, we compare to options that navigate local maxima of Node Betweenness [11], subgoal-based approach that captures the many different notions of the bottleneck concept in the literature. Similarly to the proposed approach, is also one of the few approaches in the literature to explicitly characterise a target skill hierarchy for an agent to learn. We also compare to Eigenoptions [29], which are derived from the Laplacian of the state transition
5

---

Rooms
Level 4
Level 3
Level
Level
Office
Level 5
Level 4
Level
Level
Taxi
Level
Level
Level
Level
Towers of Hanoi
Level 3
Level 2
Level
Figure 2: The cluster hierarchies produced by the Louvain algorithm when applied to the state transition graphs representing Rooms, Office, Taxi, and Towers of Hanoi. For Taxi and Towers of Hanoi, the graph layout was determined by using force-directed algorithm that models nodes as charged particles that repel each other and edges as springs that attract connected nodes.
graph and encourage efficient exploration. Finally, we include Primitivv agent that uses only primitive actions. Primitive actions are available to all agents.
We present learning curves in Figure 3. The Louvain agent has clear and substantial advantage other approaches in all domains except for Towers of Hanoi, where its performance is much closer to that of the other hierarchical agents, with none of them performing much better than the primitive agent. This is consistent with existing results reported in this domain (c.g., by Jinnai et al. [30]).
Section C of the supplementary material contains further analysis comparing Louvain skills and skills based on node betweenness.
Scaling to larger domains. We experimented with a multi-floo version of the Office environment, with floors connected by a central elevator, where two primitive actions move the agent up and down between two adjacent floors. The number of states in this domain can be varied by adjusting parame- ters such as the number of office floors. We use this environment explore how the performance of the agent and the Louvain skill hierarchy change as the number of states in the environment increases.

---

Rooms
Maze
Towers of Hanoi
12
5
Rewarrd
Rewardd
8
95
3
2
10
20
30
40
50
60
20
40
60
80
100
10
20
30
40
50
Epoch
Epoch
Epoch
Taxi
Office
Grid
20
15
15
15
Rewarrd
Rewaard
Rewward
10
Louvein
Eigenoptions Label Prop.
Bet
Node Bei
X et al.
Primitiiv
10
20
30
40
50
50
100 Epoch
150
200
20
40
80 Epoch
60
100
Epoch
Figure 3: Learning performance. An epoch corresponds to 100 decision stages in Rooms and Towers of Hanoi, 300 in Taxi, 750 Maze and Grid, and 1000 Office.
Figure 4a presents results in an Office environment with 2537 states. shows that Louvain agent learns much more quickly than all other agents. Some alternatives, including the Eigenoptions agent, fail to achieve any learning.
Figure 4b shows how the Louvain skill hierarchy changes with the size of the state space in the Office environment. The figure shows the depth of the skill hierarchy series of fifteen Office environments of increasing size, ranging from a single floor (~103 states) to one thousand floors (~100 states). The depth of the hierarchy increased very gradually with the number of states in the environment. The maximum hierarchy depth reached was eight in the largest environment tested.
Hierarchical versus flat arrangement of skills. An alternative the Louvain skill hierarchy is flat arrangement of the skills, where each skill calls primitive actions directly rather than indirectly through other (lower-level) skills. We expected the hierarchical arrangement to lead to faster learning than the flat arrangement due to the additional learning updates enabled by the hierarchical relationship between the skills. Figure shows that this indeed the case. In the figure. Louvain shows an agent that uses the Louvain skill hierarchy while Louvain flat shows an agent that uses the Louvain skills but where the skill policies call primitive actions directly rather than through other skills. In addition, the figure shows number of agents that use only a single level of the Louvain hierarchy
Reward 15
Louvain
Hierarchy Depth
8
10
7
Label Prop.
5
Edge Bet.
6
Node Bet.
Eigenoptions Primitive
100
300
10a
10 Number of States (b)
10a
10
Epoch (a)
Figure 4: (a) Learning performance in a two-floor Office containing 2537 states. (b) How the depth of the skill hierarchy scales with the size of the state space in multi-floor Office.
7

---

Rooms
Taxi
Maze
20
12
15
Rewarrd
Louvain
Reward
Resvard
Louvain flat
10
Level Primutive
15
30
45 Epoch
60
10
20
30
40
50
20
40
60
80
100
Epoch
Epoch
Figure 5: Learning curves comparing various different Louvain agents. An epoch corresponds 100 decision stages in Rooms, 300 in Taxi, and 750 in Maze. The skill hierarchy contained three levels in Rooms and Taxi, and four levels in Maze.
(Level 1, Level 2, Level or Level 4), with option policies that call primitive actions directly. Primitive actions were available to all agents. The figure shows that the hierarchical agent learns more quickly than the flat agent. Furthermore, the agents using individual levels of the Louvain hierarchy learn more quickly than the primitive agent but not as quickly as the agent using the full Louvain hierarchy.
Impact of the resolution parameter. When using very high values of the resolution parameter p. the Louvain algorithm terminates without producing any partitions. On the other hand, when using very low values of p. runs until a partition produced where all nodes are merged into a single cluster.
Figure 6 shows how changing the resolution parameter p impacts the Louvain cluster hierarchy in Towers of Hanoi and Rooms. In Towers Hanoi, at p = 10, the output is single level containing many small clusters comprised of three nodes. As p gets smaller, the cluster hicrarchy remains the same until p = 3.3, at which point a second level is added. The first level remains identical to the single level produced at 10. The second level contains larger clusters, each formed by merging three of the clusters from the first level. As p reduced further, additional levels are added the hierarchy. When new level is added to the hierarchy, the existing levels generally remain the same.
sensitivity analysis on the value of p showed that wide range of p values led useful skills, and that performance gradually decreased to no worse than that of primitive agent at higher values of p. Section E of the supplementary material contains full details of this sensitivity analysis and more detailed discussion on the choice of
6 Discussion and Future Work
An important research direction for future work is incremental learning of Louvain skill hierachies the agent interacts with its enviromeent-becaus the state transition graph will not always be available in advance. We explored the feasibility of incremental learning in the Rooms environment.
Towers of Hanoi
Rooms
Nodes Per Cluster
Level
Nodes Per Clustrr
Level
8
Level
6
Level
6
Level
8
10
10
10
10
-0
10
10a
10 10
1003
10 10
10
10a
Resolution Parameter
Resolution Parameter
Figure 6: How the Louvain algorithm's output when applied to Towers of Hanoi and Rooms changes with the resolution parameter. The cluster hierarchy had a maximum four levels in Towers of Hanoi and five levels in Rooms.

---

Rewart
Cailing
Replace
Updale
Primitive
10
30
40
50
60
Epoch
(a) Incremental Performance
(b) 30 States
(c) 60 States
(d) States
Figure 7: (a) Performance when incrementally discovering Louvain options in Rooms. An epoch corresponds to 100 decision stages. (b-d) How the state transition graph and top-level partitions produced by the Update approach evolved as agent explored Rooms. The hierarchy contained 2 levels after visiting 30 states, 3 levels after visiting 60 states, and levels after observing all possible transitions.
The results are shown in Figure 7. The agent started with an empty state transition graph and no skills. Every m decision stages, it updated its state transition graph with new nodes and edges, and it revised its skill hierarchy using one of two approaches: Replace or Update.
In the first approach (Replace), the agent applied the Louvain algorithm to create a new skill hierarchy from scratch. In the second approach (Update), the agent incorporated the new information into its existing skill hierarchy, using an approach similar to the Louvain algorithm. This second approach starts by assigning each node its cluster; the nodes are then iteratively moved locally, between neighbouring clusters (both new and existing) until no modularity gain is possible. This revised partition used to define an aggregate graph and the entire process is repeated on the aggregate graph, and the next aggregate graph, and so on, until an iteration is reached with no modularity gain. The cluster membership of existing nodes stays fixed; only new nodes have their cluster membership updated. The result of both approaches is a revised set of partitions, from which revised hierarchy of Louvain skills is derived. Section I of the supplementary material presents pseudocode for the two incremental approaches.
Figure 7a shows the performance of the incremental agents. The agents started with only primitive actions; after decision stages 100, 500, 1000, 3000, and 5000, the state transition graph was updated and the skill hierarchy agent using the full Louvain skill hierarchy, whose performance acts as a Ceil ing for the incremental agents. Both incremental agents learned much faster than the primitive agent and only marginally slower than the fully-informed Louvain agent. The two incremental agents had similar performance throughout training but Replace reached a higher level of asymptotic performance than Update, as expected. The reason is that partitions produced early in training are based on incomplete information; Replace discards these early imperfections while Update carries them forward. But there a trade- off: building a new skill hierarchy from scratch has a higher computational cost than updating an existing one.
revised. The figure compares performance to Primitive agent and an
Figures 7b-7d show the evolution of the partitions as the Update agent performed a random walk in Rooms. The partitions were updated after observing 30 states, 60 states, and all possible transitions. The figure shows that, as more nodes were added, increasingly higher-level skills were produced.
These results demonstrate the feasibility of learning Louvain skills incrementally. A full incremental method for Icarning Louvain skills may take many forms, and different approaches may be useful under different circumstances, with each having its own strengths and weaknesses. We leave the full development of such algorithms to future work.
Another direction for future work is extending Louvain skills to environments with continuous state spaces such robotic control tasks. Such domains present a difficulty to all skill discovery methods that use the state transition graph due to the inherently discrete nature of the graph. If the critical step of constructing an appropriate graphical representation a continuous state space can be achieved, all graph-based methods would benefit. Some approaches have already been proposed in the literature. We use one such approach [40, 20, 26) examine the Louvain hierarchy in a variant of the Pinball domain [41], which involves manoeuvring ball around a series of obstacles to reach goal, as

---

Pinball Layout
Level 3
Level 2
Level
Figure 8: The layout of the Pinball environment-with the green ball in its initial position, the red goal, and several obstacles-and the Louvain cluster hierarchy produced by the Louvain algorithm.
shown in the leftmost panel of Figure 8. The state is represented by two continuous values: the ball's position in the horizontal and vertical directions. At each decision stage, the agent can choose to apply a small force to the ball in each direction. The amount of force applied is stochastic and causes the ball to roll until friction causes to come a rest. Collisions between the ball and the obstacles are elastic.
We sampled 4000 states, added them to the state transition graph, then added an edge between each node and its k-nearest neighbours according to Euclidean distance, assigning an edge weight of e 4dd to an edge that connects two locations and with Euclidean distance d between them. We then applied the Louvain algorithm to the resulting graph. The result was the cluster hierarchy shown in Figure 8. It had three levels. Moving between clusters in the top level corresponds to skills that enable high-level navigation of the state space, and take into account features such as the natural bottlenecks caused by the obstacles, allowing the agent to efficiently change its position. Moving between clusters in the lower-level partitions enable more local navigation.
Currently, Louvain skills at one level of the hierarchy are composed of skills from only the previous level. Such skills may not provide the most efficient navigation between clusters. Future work could consider composing skills from all lower levels, including primitive actions.
Because Louvain skills are derived from the connectivity of the state transition graph, we expect them to be suitable for solving a range of problems in a given environment. Examining their use for transfer learning useful direction for future work.
possible difficulty with building multi-level skill hierarchies that having a large number of skills can end up hurting performance by increasing the branching factor. One solution that has been explored in the context of two-level hicrarchies is pruning less useful skills from the hierarchy [21, 42]. Further research is needed to address this potential difficulty.
key open problem for graph-based skill discovery methods generally is how best make use of state abstraction. We suggest that the most natural place to introduce state abstraction is when constructing the state transition graph itself. Instead of concrete state, each node could represent an abstract state based on some learned representation of the environment. The proposed method and any other existing graph-based method-coul then directly use this abstract state transition graph to define a skill hierarchy.
Lastly, we note that the various characterisations of useful skills proposed in the literature, including the one proposed here, are not necessarily competitors. To solve complex tasks, it is likely that an agent will need use many different types of skills. An important avenue for future work exploring how different ideas on skills discovery can be used together to enable agents that can autonomously develop complex and varied skill hierarchies.
Acknowledgments and Disclosure of Funding
We would like to thank the members of the Bath Reinforcement Learning Laboratory for their constructive feedback. This research was supported by the Engineering and Physical Sciences Research Council [FP/R513155/1 and the University of Bath. This research made use of Hex, the GPU Cloud in the Department of Computer Science the University of Bath.
10

---

References
[1] R. S. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 11211-2)11,,-11, 1999.
[2] D. Precup. Temporal abstraction in reinforcement learning. PhD thesis, University of Mas- sachusetts Amherst, 2000.
[3] M. E. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2):266 13, 2004.
[4] E. A. Leicht and M. E. Newman. Community structure in directed networks. Physical Review 2008.
Letters, (00((1):11888)
[5] A. Arenas, J. Duch, A. Feránndez, and S. Gómez. Size reduction of complex networks preserving modularity, New Journal of Physics, 96)):76,, 2007.
[6] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, and D. Wagner. Maximizing modularity is hard. arXiv preprintpphsices0008555. 2006.
[7] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):10009) 2008.
[8] A. Lancichinetti and S. Fortunato. Community detection algorithms: a comparative analysis. Physical Review E, 80(5)00661 17, 2009.
[9] I. Menache, S. Mannor, and N. Shimkin. Q-Cut D-Cut-Da -ynt-Dyaamic discovery of sub-goals in rein- forcement learning. In Proceedings of the 13th European Conference on Machine Learning, ECML '02, pages 295-306. Springer- Verlag, 2002.
[10] Ö. Şimşek and A. G. Barto. Using relative novelty identify useful temporal abstractions in reinforcement learning. In Proceedingy of the 2 International Conference on Machine Learning, ICML '04, pages 95-102. ACM, 2004.
[11] Ö. Şimşek and A. G. Barto. Skill characterization based on betweenness. In Advances in Neural Information Processing Systems 21, NeurlPS '09, pages 1497-1504. Curran Associates, Inc., 2009.
[12] Moradi, M. Shiri, and N. Entezari. Automatic skill acquisition in reinforcement learning agents using connection bridge centrality. In International Conference on Future Generation Communication and Networking, pages 51-62. Springer, 2010.
[13] A. A. Rad. M. Hasler, and Moradi. Automatic skill acquisition in reinforcement learning using connection graph stability centrality. In Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pages 697-700. IEEE, 2010.
[14] M. A. Imanian and Moradi. Autonomous subgoal discovery in reinforcement learning agents using bridgeness centrality measure. International Journal of Electrical and Computer Sciences, 11(5):54-68 62, 2011.
[15] Moradi, M. E. Shiri, A. A. Rad, A. Khadivi, and M. Hasler. Automatic skill acquisition in reinforcement learning using graph centrality measures. Intelligent Data Analysis, 16(1): 113-135, 2012.
[16] H. Metzen. Online skill discovery using graph- clustering. Proceedings of the Tenth European Workshop on Reinforcement Learning. EWRL '13, pages 77-88. PMLR, 2013.
[17) Ò. Şimşek, A. P. Wolfe, and A. G. Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd International Conference on Machine learning, ICML '05, pages 816-828. 823. ACM, 2005.
[18] J. Kazemitabar and H. Beigy. Using strongly connected components basis for autonomous skill acquisition reinforcement learning. In 6th International Symposium on Neural Networks, ISSN '09, pages 794-803. Springer, 2009.

---

[19] N. Entezari, M. E. Shiri, and P. Moradi. A local graph clustering algorithm for discover- ing subgoals in reinforcement learning. In International Conference on Future Generation Communication and Networking, pages 41-50. Springer, 2010.
[20] P.-L.. Bacon and D. Precup. Using label propagation for learning temporally abstract actions in reinforcement learning. In Proceedings of the Workshop on Mulliagent Interaction Networks, MAIN 13, 2013.
[21] N. Taghizadeh and H. Beigy. A novel graphical approach to automatic abstraction in reinforce- ment learning. Robotics and Autonomous Systems, 61(8):821-835 2013.
[22] S. J. Kazemitabar, N. Taghizadeh, and H. Beigy. A graph-theoretic approach toward autonomous skill acquisition in reinforcement learning. Evolving Systems, 93))2277-244, 2018.
[23] R. Ramesh, M. Tomar, and B. Ravindran. Successor options: option discovery framework for reinforcement learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCA 19, pages 3304-3311 AAAI Press, 2019.
[24] S. Mannor, I. Menache, A. Hoze, and U. Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the 21st International Conference on Machine Learning, ICML '04, pages 7 71-78. ACM, 2004.
[25] M. Davoodabadi and H. Beigy. A new method for discovering subgoals and constructing options in reinforcement learning. In Proceedings of the 5th Indian International Conference on Artificial Intelligence, pages 441-450, 2011.
[26] F. Shoeleh and M. Asadpour. Graph based skill acquisition and transfer learning for continuous reinforcement learning domains. Pattern Recognition Letters, 87:104-116, 2017.
[27] X. Xu, M. Yang, and G. Li. Constructing temporally extended actions through incremental community detection. Computational Intelligence and Neuroscience, 2018.
[28] M. D. Farahani and N. Mozayani. Automatic construction and evaluation of macro-actions in reinforcement learning. Applied Soft Computing, 82: 105574, 2019.
[29] M. C. Machado, M. G. Bellemare, and M. Bowling. A Laplacian framework for option discovery in reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, ICML 17,, pages
PMLR, 2017.
[30] Y. Jinnai, J. W. Park, D. Abel, and G. Konidaris. Discovering options for exploration by minimizing cover time. In Proceedings of the 36th International Conference on Machine Learning, ICML '19, pages 3130-3139, PMLR, 2019.
[31] P.-L. Bacon, J. Harb, and D. Precup. The option-critic architecture. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017
[32] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforce- ment learning with function approximation. In Advances in Neural Information Processing Systems 12, NeurlPS '99. MIT Press, 1999.
[33] M. Riemer, M. Liu, and G. Tesauro. Learning abstract options. In Advances in Neural Information Processing Systems 31, NeurIPS '18. Curran Associates, Inc., 2018
[34] R. Fox, S. Krishman, I. Stoica, and K. Goldberg, Multi-level discovery of deep options. arXiv preprint: 1703, 08294, 2017.
[35] A. Levy, G. Konidaris, R. Platt, and K. Saenko. Learning multi-level hierarchies with hindsight. In Proceedings of the 7th International Conference on Learning Representations, ICLR '19 2019.
[36] G. Dietterich. Hierarchical reinforcement learning with the MAXQ value function decompo- sition. Journal of Artificial Intelligence Resesearch, 13(1):227-303, 2000.
12

---

[37] A. McGovern, R. S. Sutton, and A. H. Fagg. Roles of macro-actions in accelerating reinforce- ment learning. In Grace Hopper Celebration of Women Computing, volume 1, pages 13-18, 1997.
[38] R. S. Sutton and D. Precup. Intra-option learning about temporally abstract actions. In Proceedings the 15th International Conference on Machine Learning, pages 556-564. Morgan Kaufman, 1998.
[39] C. C. H. Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge United Kingdom, 1989.
[40] S. Mahadevan and M. Maggioni. Proto-value functions: A Laplacian framework for learning representation and control in Markov decision processes. Journal of Machine Learning Research, 8(10), 2007.
[41] G. Konidaris and A. Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. In Advances Neural Information Processing Systems 22, NeurIPS '09, pages 1015-1023, Curran Associates, Inc., 2009.
[42] D. M. Farahani and N. Mozayani. Evaluating skills in hierarchical reinforcement learning. International Journal of Machine Learning and Cybernetics, 11(10))2407-2422 2020.
13


Reviews:
[{"review_id": "wlUsMFTOR6", "reviewer": "Reviewer_cG6b", "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.", "questions": "- Why did the authors select Q-learning as the baseline for primitive actions instead of a more recent, and better-performing, algorithm?\n- It seems like the first two plots of Figure 4 do not present the results for Level 4. Could the authors please clarify this?\n- 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?", "limitations": "The authors discuss the limitations of the work. No major concerns.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n- The proposed method is intuitive and has a different/creative look at a problem that has not been solved yet. \nThe paper is very clearly written, with a very good display of the empirical results, analyzing both qualitative and quantitative aspects of the learned skills.\n- 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).\n- 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.\n", "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.\n- 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).\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time and attention you have given to our paper. \n\n**Q1: Why did the authors select Q-learning as the baseline for primitive actions instead of a more recent, and better-performing, algorithm?**\n\nThe main point of the baseline algorithm is to allow a comparison of the agent's performance with and without Louvain skills. Louvain skills themselves are agnostic to any particular hierarchical reinforcement learning algorithm, so we could have performed our analysis with any algorithm as long as it had a primitive counterpart we could use for our comparison.\n\nLouvain skills are based on the graphical structure of an agent's interaction with its environment; so the most natural test of their fundamental utility is in environments with discrete states and discrete actions. We used Q-learning as the baseline because (1) it is a suitable algorithm for such environments, and (2) it is the direct primitive counterpart to macro-Q learning and intra-option learning, which we used to train the hierarchical agents.\n\n**Q2: It seems like the first two plots of Figure 4 do not present the results for Level 4. Could the authors please clarify this?**\n\nWe used a single legend for all three plots in Figure 4. We now see that this created confusion and will remedy it. In the domains shown in the first two plots (Rooms and Taxi), the Louvain skill hierarchy contained only three levels, so there was no \"Level 4\" agent.\n\n**Q3: Currently, 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?**\n\nFor stochastic MDPs, it would be appropriate to weight edges according to the probability of the underlying transition. Many edge-weighting schemes have been proposed in the graph-based skill discovery literature (e.g., see Section 3.1, Metzen (2013)). One sensible approach is to assign an edge from state $u$ to state $v$ a weight of $\\sum_{a \\in A(u)}P(u,a,v)$. These probabilities could be based on the true transition probabilities, if known, or could otherwise be estimated from experience.\n\nThe definition of modularity naturally handles weighted graphs, so the Louvain algorithm (and, therefore, the proposed method) will be able to use this information. The higher the probability of transitioning between two states, the higher the weight of the edge between them, and the higher the likelihood that the Louvain algorithm will place these two states in the same cluster.\n\n**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).**\n\nMaking a large set of options available to the agent can indeed harm learning. But Louvain skills have a number of useful properties that limit the impact of this problem.\n\nFirst, we observe empirically that the depth of the Louvain skill hierarchy grows very slowly with the size of the state space. Figure 4b shows that the hierarchy depth increases from 5 levels in a version of Office with 1000 states to 8 levels in a version of Office with over 1 million states. This aligns with existing results reported in the literature, such as from Blondel et al. (2008), who find that the Louvain algorithm produced 6 levels when applied to a graph of a social network with over 2 million nodes.\n\nSecondly, two parameters influence the depth of the Louvain skill hierarchy: the resolution parameter, $\\rho$, and the mean cluster size threshold, $c$.\nHigher values of $\\rho$ punish overall cluster size and inter-cluster edges more harshly, leading the Louvain algorithm to run for fewer iterations and produce fewer partitions. The result is a skill hierarchy with fewer levels.\nOn the other hand, $c$ impacts the lowest level of the hierarchy — the algorithm discards partitions containing clusters that are (on average) smaller than $c$. Higher values of $c$ lead to more partitions being discarded, resulting in a skill hierarchy with fewer levels.\n\nThirdly, although many skills may be defined at each level of the hierarchy, a relatively small number of them will be available in any given state. This is because Louvain skills have restricted initiation sets: a Louvain skill navigating from some source cluster to some target cluster is available only in the states of the source cluster. For example, in Rooms, at level 2 of the hierarchy, at most 3 skills are available from each state (See Figure 2, top row, third column).\n\nFinally, arranging Louvain skills into a multi-level hierarchy allows an agent to learn about multiple skills at the same time. When an agent is executing a skill, it learns about the consequences of executing not only that specific skill but also of any of the lower-level skills (and, ultimately, primitive actions) that the skill calls upon while executing.\n\n**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.**\n\nIncorporating the task reward when producing Louvain skills would be an interesting avenue for future work. But Louvain skills as defined in the paper, based purely on the connectivity of the state-transition graph, are still useful. In large state spaces, in the absence of further information on where the rewards may be, they will allow efficient exploration of the state space. In our experiments, Louvain skills helped learning efficiency the most in the largest domain we tested (Figure 5c).\n"}, {"review_id": "nHrz7eBpl4", "reviewer": "Reviewer_4HvS", "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.  ", "questions": "The paper is very clear.  Other than the weakness mentioned above, I do not feel I have pressing questions.", "limitations": "Limitations are more than adequately addressed, as mentioned in the strengths section above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n- Comparison with baselines.  The paper describes five alternative graph-based approaches, and shows superior performance of the Louvain-based method.  \n\n- 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.  \n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time and attention you have given to our paper. \n\n**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.**\n\nThank you for pointing out the need for additional clarification. We provided full experimental details in the supplementary material (Appendix F) and will expand on this specific point in the main paper.\n\nConsider a Louvain option for moving from cluster $c_i$ to a neighbouring cluster $c_j$. To train the policy of this option, macro-Q learning was applied to the following task: the agent starts in a random state in cluster $c_i$; it receives a reward of $-0.01$ at each decision stage until it reaches a state in cluster $c_j$, where it receives a reward of $+1.0$ and the episode terminates. After many episodes of training, this produces an option policy that efficiently takes the agent from any state in $c_i$ to the cluster $c_j$. The policies of options at level $i$ of the hierarchy, $i > 1$, call only the options from level $i-1$; the policies of options at level 1 call only the primitive actions. \n\nThis is just one example of how Louvain option policies can be trained. Other approaches exist. Our analysis focused on exploring how useful Louvain options are when available to an agent; therefore, precisely how the option policies were trained did not matter as long as the learned policies were correct.\n"}, {"review_id": "IXTW5kAKwb", "reviewer": "Reviewer_7zy2", "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.\n\nThe 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.  ", "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.\n\n(II) How can state abstraction be employed using the proposed method?\n\n(III) Can the current method handle continuous state space problems?\n\n(IV) How does the proposed work relate to [1]?\n\n(V) In empirical evaluation, how is the office world (without any objects) different from the maze world domain? \n\n(VI) Can you comment about scalability of the approach to handle domains with large state spaces?\n\n(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?\n\n\nReferences:\n\n[1] Fox, R., Krishnan, S., Stoica, I. and Goldberg, K., 2017. Multi-level discovery of deep options. arXiv preprint arXiv:1703.08294.\n", "limitations": "(Included in summary, weaknesses)", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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. \n\n(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.  \n\n(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. \n\n(IV) An analysis of comparison of the number of samples required by each baseline to learn a hierarchy and option policies is needed.\n\n\nMinor:\n\n(I) line 20: has -> have\n\n(II) line 112: the partition -> the partition c_i is\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time and attention you have given to our paper.\n\n**Q1: Can you explain “we use each of the h partitions to define a single layer of skills, resulting in a hierarchy of h levels”?**\n\nWe will give an example using Figure 2 in the paper. In Rooms, the algorithm produces 4 partitions of the state space, as shown in the top row of Figure 2. Consider the \"Level 4\" partition. This partition defines level 4 of the skill hierarchy, which has 6 skills: 1) from purple to green, 2) from purple to yellow, 3) from green to yellow, and so on. Similarly, the \"Level 3\" partition defines level 3 of the skill hierarchy, which has 8 skills: 1) from yellow to blue, 2) from yellow to green, 3) from blue to red, and so on. Similarly, the Level 2 and Level 1 partitions, respectively, define level 2 and level 1 of the skill hierarchy. (At the very bottom of the skill hierarchy, which could be called level 0, we have the primitive actions.)\n\n**Q2: How can state abstraction be employed using the proposed method?**\n\nThe most natural place to introduce state abstraction would be when constructing the state-transition graph. Instead of a concrete state, each node could represent an *abstract* state based on some learned representation of the environment, and the Louvain algorithm could be applied to this abstract state-transition graph.\n\nWe also note that how to employ state abstraction is an important open problem for graph-based skill discovery generally. Any promising methodology could be directly incorporated into the discovery of Louvain skills.\n\n**Q3: Can the current method handle continuous state space problems?**\n\nPreliminary results in the paper suggest that it can (see Figure 7). We explored one possible approach for building a state-transition graph to represent a continuous domain, and we partitioned the graph by using the Louvain algorithm to form the basis of a concrete set of Louvain skills.\n\n**Q4: How does the proposed work relate to Fox et al. (2017)?**\n\nFox et al. (2017) propose DDO, an imitation learning method that extracts option hierarchies from demonstration trajectories. It uses policy-gradient methods to train option policies and termination conditions that are most likely to generate given demonstration trajectories. This is fundamentally very different to our approach.\n\nDDO requires demonstration trajectories; our approach does not. With DDO, both the number of hierarchy levels and the number of options per level need to be specified by the system designer ahead of training. In contrast, our proposed approach automatically finds a suitable number of hierarchy levels and automatically produces a suitable number of skills at each level. Furthermore, using an incremental version of our method, the number of hierarchy levels and skills per level can evolve during training.\n\n**Q5: How is the office world (without any objects) different from the maze world domain?**\n\nThe dynamics of Office are the same as the other gridworlds (except for the elevator tile). We designed Office to be able to explore the scaling properties of our approach as the number of states increases (see figures 5b and 5c).\n\n**Q6: Can you comment about scalability of the approach (…)?**\n\nOur main contribution is a novel characterisation of a useful skill hierarchy based on the concept of modularity. This contribution, we believe, scales to large state spaces conceptually.\n\nAs the size of the state space increases, we will need to consider different ways of representing the graphical structure of the environment (direct use of the state-transition graph will not be useful). We expect that future work will identify and explore different approaches with different strengths and weaknesses under different conditions.\n\nThe Louvain algorithm itself scales well to large graphs. Blondel et al. (2008) successfully applied it to graphs with millions of nodes and billions of edges and observed its time complexity to be linear in the number of graph edges. We also successfully applied it to versions of Office with over 1 million states.\n\n**Q7: Do the baselines assume a state transition graph or start learning from scratch? How many samples were required to learn the hierarchies by different methods along with the samples required to learn the option policies?**\n\nAll baselines assumed access to the complete state-transition graph.\n\nOur analysis focused on the comparative benefits of the learned skills – because the fundamental question we are asking is *what is a good skill hierarchy?* – so we did not measure the number of samples required by the different methods. All that mattered was that the skills were accurately learned in each case.\n\nPlease note that there is no single number of samples required by each algorithm: more samples generally lead to better learning of the underlying concept; so, for each algorithm, there is a range (of number of samples) for which the learned skills are useful to varying degrees.\n\n**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.**\n\nThank you, we will make sure that the assumptions in the different parts of the paper are clearly stated.\n\nWhen testing the utility of the general concept (Louvain skills), we assume that the graph is available. When exploring incremental learning algorithms, we do not make that assumption.\n\nThe most direct use of the Louvain algorithm assumes discrete state and action spaces. But our characterisation of a useful skill hierarchy (based on modularity) is a general concept that can be used with abstract or approximate versions of a state-transition graph. Fundamentally, all that is required is a graphical representation of an agent's interaction with its environment – given or learned, exact or approximate, complete or partial, etc. – that encodes what is known about the connective structure of this interaction.\n"}, {"review_id": "URyVhmKtNN", "reviewer": "Reviewer_UjdQ", "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.", "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?\n\nI 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.\n\nThere are too many confusing descriptions, including:\n\n•\t\"an autonomous agent\" in Line1\n\n•\t\"graphical structure\" in Line2\n\n•\t\"its environment\" in Line2\n\n•\t\"multiple levels of abstraction\" in Line4\n\n•\t\"regions of the state\" in Line5\n\n•\t\"connected within themselves\" in Line6\n\n•\t\"various levels of granularity\" in Line16\n\n•\t\"outcome\" in Line17\n\n•\t\"characterisation\" in Line19\n\n•\t\"existing approaches to skill discovery\" in Line55\n\n•\t\"are not without their limitations\" in Line72\n", "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.\n\nLouvain 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.\n\nI 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.\n", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 1, "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.\n\nThis 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.\n\nIn 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time and attention you have given to our paper.\n\nLA: Louvain Algorithm\n\n**Q1: 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?**\n\nWe see consistently, across domains, that the learning efficiency increases when Louvain skills are available to the agent (Figure 3). We also see that the learning efficiency gained from Louvain skills (compared to primitive actions) increases with the size of the domain: the largest performance gap between the Louvain agent and the primitive agent is in the largest domain we tested (Figure 5c). \n\n**Q2: 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.**\n\nIt is possible we do not understand what you mean by diversity because we are confused by this question. There is in fact significant diversity in the Louvain skills.\n\nFor example, consider the *Level 3* skills in Rooms (see Figure 2, top row). There are 8 skills at this level, two from each room, and each of these skills takes the agent in a different direction. For instance, in the upper-left room (depicted in green), two skills can be initiated: one (efficiently) takes the agent to the upper-right room (red) and the other to the lower-left room (yellow). And this is only the diversity at level 3 of the skill hierarchy. Skills at other levels of the hierarchy are similarly diverse but, *in addition*, they introduce diversity in the skills’ reach (trajectory length; the degree of temporal abstraction). For instance, Level 2 skills are shorter (in trajectory length), and Level 1 skills are even shorter, than Level 3 skills.\n\nIn summary, we see diversity in skill initiation sets, skill policies, and trajectory lengths. Furthermore, collectively, the skills cover the state space very well.\n\n**Q3: There are too many confusing descriptions (...)**\n\nWe are sorry to hear this and would very much like to remedy it. At the same time, we are unsure what is confusing about the words and phrases you have highlighted. Many, such as *autonomous agent* and *environment*, are fundamental concepts in reinforcement learning. Others, such as *graphical structure* are clearly illustrated in the paper. We would welcome any concrete comments that would help us improve the writing.\n\n**[Skill discovery] is extremely difficult and could not be well solved by introducing Louvain-based graph clustering methods as described in the paper.**\n\nWe agree, skill discovery is very difficult. This is exactly why it is important to explore a wide variety of approaches and to not prematurely discard any of them, especially ones that show promise in small-scale problems, such as the one we propose here.\n\nWe strongly oppose the statement that skill discovery cannot be solved by introducing Louvain-based graph clustering methods. There is no basis for this statement. Skill discovery is an open problem and Louvain-based graph clustering methods may well be part of the solution.\n\n**The Louvain algorithm has been proposed in 2008 and there have been a lot of improved works during 2010-2015 (...) [it] should not be the focus of the paper.**\n\nLA remains one of the most popular and highly-performing modularity optimisation algorithms. Although several improvements have been proposed to its original formulation, most of these modifications improve the algorithm’s runtime but do not impact its final output. Those modifications that do modify its output often result in the hierarchical structure being harder to extract, and this makes them unsuitable for our purposes.\n\nWe explain LA in the paper because otherwise the skill hierarchy it generates would not be as clear to the reader.\n\n**Agents’ skills should be learned in more complex scenarios with more constraints, such as StarCraft II and the Minecraft (...)**\n\nThis is an unrealistically high bar. Adopting it would be detrimental to research progress on this very important subject, and this is recognised by the research community: Papers on skill discovery are continuously being published at NeurIPS and other high-profile venues, such as ICML; we are not aware of a single paper that meets this bar. In fact, many new ideas are presented and tested in small, discrete domains. e.g., Bar, Talmon, & Meir (ICML 2020), Jinnai et al. (ICML 2019).\n\n**Finally, we would like to respond to the 3 limitations raised by the reviewer.**\n\n1a. Factual correction: skill-based approaches do converge to the global optimal solution. If primitive actions are included in an agent’s action set along with skills (as we have done), then existing convergence guarantees from the primitive-only case continue to hold. Some HRL frameworks might lose global convergence (e.g., MAX-Q) but not the options framework (see Precup, Sutton & Singh, Theoretical results on RL with temporally abstract options, ECML, 1998).\n\n1b. Theoretically analysing the learning efficiency of agents using a specific skill hierarchy is difficult: such analysis is not present even in the most well-known skill discovery papers. We argue that this is not a reasonable requirement from the paper.\n\n2a. The relationship between LA and RL is simple: LA provides input to RL.\n\n2b. Clustering by LA does indeed guide RL: it impacts exploration; it determines what the skills are and skills are part of the policy learned by RL.\n\n2c. RL does not inform LA, but why is this a weakness?\n\n2d. You may find it useful to see the discussion of reward at the end of our rebuttal to Reviewer cG6b.\n\n3. The paper should not be evaluated as a skill discovery algorithm. We are not presenting a skill discovery algorithm but a hypothesis on what makes a useful skill hierarchy. To evaluate this hypothesis, we necessarily use the transition graph. We took great care in writing the paper to make this point clearly and repeatedly.\n"}]

Author rebuttal:

Meta-review: There was near consensus among the reviewers to accept this paper, praising its novelty, intuitive appeal, clarity, and the thoroughness of the discussion of the results. Several reviewers raised a concern regarding the requirement that the state-transition graph is known, to which the authors pointed out that this is only true for a fraction of the experiments, and that the incremental learning algorithms go beyond this restriction. Further, reviewers initially disagreed about the quality of the empirical valuation, with some praising the diversity and breadth of the experimental domains and others calling for further diversity. The discussion largely resolved the primary concerns of most reviewers. Thus, I believe the strengths outweigh the weaknesses, and I recommend this paper be accepted
Decision: Accept (poster)