Exploration in Reinforcement Learning with Deep Covering Options
Authors: Yuu Jinnai
Jee Won Park
Marlos C. Machado
George Konidaris
Venue:  (2020)
Keywords: Reinforcement learning
temporal abstraction
exploration

Abstract: While many option discovery methods have been proposed to accelerate exploration in reinforcement learning, they are often heuristic. Recently, covering options was proposed to discover a set of options that provably reduce the upper bound of the environment's cover time, a measure of the difficulty of exploration. Covering options are computed using the eigenvectors of the graph Laplacian, but they are constrained to tabular tasks and are not applicable to tasks with large or continuous state-spaces. 
We introduce deep covering options, an online method that extends covering options to large state spaces,  automatically discovering task-agnostic options that encourage exploration. We evaluate our method in several challenging sparse-reward domains and we show that our approach identifies less explored regions of the state-space and successfully generates options to visit these regions, substantially improving both the exploration and the total accumulated reward.

Published as a conference paper at ICLR 2020
EXPLORATION IN REINFORCEMENT LEARNING WITH DEEP COVERING OPTIONS
Yuu Jinnai Brown University
Jee Won Park Brown University
Marlos C. Machado Google Brain
George Konidaris Brown University
ABSTRACT
While many option discovery methods have been proposed to accelerate exploration in reinforcement learning. they are often heuristic. Recently, covering options was proposed to discover set of options that provably reduce the upper bound of the environment's s cover time, a measure of the difficulty of exploration. However, they are constrained to tabular tasks and are not applicable to tasks with large continuous state-spaces. We introduce deep covering options, an online method that extends covering options to large state spaces, automatically discovering task- agnostic options that encourage exploration. We evaluate our method in several challenging sparse-reward domains and show that our approach identifies less explored regions of the state-space and successfully generates options to visit these regions, substantially improving both the exploration and the total accumulated reward.
INTRODUCTION
Temporal abstraction, often formalized via the options framework (Sutton et al. 1999), has the potential to greatly improve the performance of reinforcement learning (RL) agents by representing actions at different time scales. However, the question of which options an agent should construct, and the related question of what objective function that option construction process should be optimizing, remain open. One recent approach is to construct options that aid exploration by providing agents with more decisive behavior than the dithering common to random exploration (e.g., Menache et al.. (00olStoolle and Precup, 2002 [Sişşek and Barto 2004, Şimsek et al. 2005 Simşek and Barto 22099] Machado et al. 2017; bysenbach et al. 2019). The Laplacian (Chung 1996), the matrix extracted from the graph induced by the agent's & policy and the dynamics of the environment, is often used when discovering options for exploration (e.g.. Machado (acha.oaa and Bowling 2016 Machado et al. 2017 2018
Jinnai et al. 2019b). The options discovered with such an approach encourage agents to navigate to parts of the state space that are infrequently visited. However, the existing methods either lack a principled way of constraining the number of discovered options (e.g.. Machado and Bowling) 2016
Machado et al. 2017 2018) or are limited to the tabular setting (e.g., Jinnai et al. 2019b).
In this paper show how recent developments in eigenfunction estimation of the Laplacian (Wu eet al.] 2019) can be used to extend a principled approach for option discovery (Jinnai et al.) 2019h) to the non-linear function approximation case. This new algorithm for option discovery, deep covering options, is computationally tractable and it is applicable to environments with large (or continuous) state-spaces. Despite methods that learn representations generally being more flexible, more scalable, and often leading to better performance, before this paper, covering options could not be easily combined with modern representation learning techniques. Deep covering options discovers a small set of options that encourage exploration by minimizing the agent's expected cover time- the expected number of steps required to visit every state the environment (Broder and Karlin 1989). Moreover, unlike most previous approaches to discovering options for exploration, it can be applied to both settings where a pretraining (unsupervised) phase is available (e.g., Eysenbach et al.) 2019) and to the traditional, fully online, setting.
We evaluate our method, in both settings, in three different platforms to demonstrate its applicability in wide range of domains. First, we apply it to the Pinball domain (Konidaris and Barto! 2009). which has a discrete action-space and continuous state-space. Second, we apply it to three MuloCo control tasks Todorov al. 2012), which are continuous state- and action-space domains. In all of

---

Published as a conference paper at ICLR 2020
these domains, method improves over the baseline. Finally, perform qualitative analysis of our method in three Atari 2600 games (Bellemare et al. (2033) to demonstrate its potential in domains with very large state-spaces. Deep covering options successfully finds under-explored regions of the state space and builds options to target those regions.
BACKGROUND AND RELATED WORK
We assume the standard reinforcement learning setting (Sutton and Barto 1998), where the environ-
ment is modeled as Markov Decision Process (MDP), (S, T, R, y), where is the set of states, A is the set of actions, T': A 8 + [0, 1] is the state transition function, R S x A + IR the reward function, and 0 S S is the discount factor.
We use the options framework (Sutton et al. 1999) to represent temporally extended actions. defines an option as triple (I, ,, B), where I C S is the set of states in which the option can initiate, S - Pr(AA) the policy the agent follows when that option is being executed, and 3 : - [0, 1]. is the termination condition. We refer to set of states in which ((s) = 1 as termination set.
2.1 RELATED WORK
Many option discovery algorithms are based on the reward signals generated by the environment and are thus task dependent. These methods often decompose the trajectories reaching the rewarding states into options. Several papers have proposed generating options from trajectories reaching these
rewarding states (e.g.. McGovern and Barto 2001 Menache et al. 2002 Konidaris and Barto 2009). while other approaches use the observed rewards to generate options with gradient descent (c.g.. Mankowitz al., 2016; |Bcon al. 2017 Harb al., [018]] Tiwari and Thomas 2019). These approaches are often ineffective in sparse reward problems, where only a few state-action pairs lead positive reward.
Fewer papers have tackled the problem of option discovery for exploration without using reward signals. [Eyeebbach al. (2019) proposed generate options maximizing information theoretic objective so that each option generates diverse behavior. While many option discovery methods are limited to discrete state and action space tasks, their method can generate options that solve many continuous control tasks, even when ignoring the environment's 's reward function. Machado et al. Machado et al. (2017: 2018) proposed eigenoptions, method to generate options using the Laplacian eigenvectors (Chung 1996). Their approach is similar to covering options but requires the set of options to be orthogonal to each other and introduces prohibitively large number of options at each iteration. Several papers have proposed identifying subgoal states without reward information through graph concepts such as clustering (Menache et al. 2002] Şimşek et al., (2055), visitation statistics (Simyek and Barto 2004: (Stole and Precup/ 2002). and betweenness centrality (Simzek) and Barto| 2009).. As they use graph algorithms to discover subgoals, their scope often limited to tabular domains.
2.2 COVERING OPTIONS
Covering options (Jinnai et al. 2019b) is an approach that minimizes the expected cover time of uniformly random policy by augmenting the agent's action with options obtained from the eigenvector associated with the second smallest eigenvalue of the Laplacian. Covering options can be seen as increasing the likelihood that random walk is going lead rewarding state since the expected cover time is the time required for a random walk to visit all the vertices in a graph (Broder and Karlin 1989). Covering options achieves such an objective by minimizing the upper bound of the expected cover time, E[C(G)), which is given by the second smallest eigenvalue of the normalized Laplacian, X2, also known as the algebraic connectivity (Fiedler 1973):
n² In (1+ (1))
B[C(G)] S
A2
where n is the number vertices of the graph. Equation [ shows that the larger the algebraic connectivity, the smaller the upper bound of the expected cover time.
Intuitively, algebraic connectivity represents how densely the graph is connected. The eigenvector f corresponding dg is an embedding of graph one-dimensional interval where nodes connected
2

---

Published as a conference paper at ICLR 2020
100
15. 7.5
000
The distance between the red state and all other states, measured via the second eigen- vector (left) and Euclidean distance (right). The second eigenvector captures the connectivity of the graph, so distances reflect path lengths in the graph; the pair of nodes with the maximum and minimum values are the farthest apart. Figure is adapted from Jinnai et al. (2019b), Figure 2.
Figure 1:
Comparison between options gener- ated by deep covering options (left) and covering options (right). Blue regions represent states in the initiation set and shaded regions states in the termination set. Generated options have initiation and termination sets consisting of single state, making them impractical in large state- spaces.
Figure 2:
by an edge tend to be placed nearby (see Figure [ adapted from Jinnai et al. 2019b). pair of nodes with the maximum and minimum value in f the most distant nodes in the embedding space. Connecting these two nodes greedily maximizes the algebraic connectivity to a first order approximation (Ghosh and Boyd 2006). Covering options works follows:
1. Compute the second smallest eigenvalue and the corresponding eigenvector f of the Lapla- cian exactly by solving the following constraint optimization problem:
A2
inf
G(F)
G(f) =
Σ f(s'))
(2)
ATA
(TA
where A is the adjacency matrix of the state-space graph where the entry at (s, 8') is if and s' are adjacent and 0 otherwise.
2. Let it and vy be the state with largest and smallest value in the eigenvector respectively. Generate two options; one with I = {wi and B = {wy} and the other one with I = {u;} and [us Each option policy is the optimal path from the initial state the termination state.
3. Set G + GU ((), and repeat the process until the number of options reaches threshold.
While this method is efficient algorithm with performance guarantees, it is limited to small discrete MDPs as it requires state-space graph. Moreover, explicitly computing the matrix that encodes the environment's adjacency matrix unrealistic beyond small problems. Finally, the method is constrained to point options where both the initiation and termination sets consist of a single state (Jinnai et al. 2019a). Options generated by this method are therefore only executable at single state. This is not useful for tasks with large (or continuous) state-spaces as the probability of visiting the state the initiation set the option tends to zero. Even the agent visits the state in the option's initiation set and starts following the corresponding option's 'ss policy, the probability of reaching the state in the termination set is also small (see Figure 2}. the next section we introduce an approach that addresses these limitations.
DEEP COVERING OPTIONS
We propose deep covering options, a new algorithm that finds options that speed-up exploration in domains with large (or continuous) state-spaces. It directly seeks to optimize an objective for exploration. If the objective function is optimized, the options generated by the algorithm greedily maximize the algebraic connectivity of the underlying state-space graph to first order approximation (Ghosh and Boyd, 2006), which in turn minimize the upper bound on the expected cover time. Deep covering options consists of four steps (see Algorithm|

---

Published as a conference paper at ICLR 2020
Algorithm Deep covering options
1: Input: Set of state-transitions H. percentile 0 S k < 100
2: Compute by minimizing G(J") using H (Equation 5)
3: / k-th percentile value of H
((s)<
4: (o(s) 10
otherwise
5: + {s]Ba(s) 0, $}
6: Train To off-policy by maximizing the total accumulated pseudo-rewards vo s(s) - f(5)
using H. and
7:
Return (Io: Tox 5o)
1. compute eigenfunction of the Laplacian of the state-space graph approximately (line 2 in Algorithm!] I
2. identify an under-explored region in the state-space using the eigenfunctions (line 3),
3. set the under-explored region the termination set and the compliment of it as the initiation set (line 4, 5),
4. train policy of the option using the pseudo-reward induced by the eigenfunctions (line 6).
There are two problems Equation that prevent its applicability to non-tabular domains. First, equation requires the adjacency matrix A as input. Second, constrained optimization problem is hard to solve using gradient-basee methods. We address these issues by approximating the computation of the Laplacian with the following objective (Wu et al., 2019 Equation 6):
f2,.,
E
(f((s)-f((s)) fc((7))
k=1
1/E smpppr
-()) -5x)]
(3)
where the set of sampled state-transitions, p is distribution of states dataset (p(s) ) the number of occurrence of 8 in H divided by the size of H), 7) is the Lagrange multiplier, and 65k is j # & and 0 otherwise. Such an expression, inspired by spectral graph drawing theory, uses the repulsive term (the summation multiplied by 7)) to ensure the functions f1, .i., fa are orthogonal to each other. Unlike G, G is constraint- objective compute the eigenfunction, only requiring trajectories instead of the state-space graph.
As only require the second eigenfunction (unlike eigenoptions), simplify the objective function to take only two arguments:
G(Ji,f2) = G()1, + -.Eepp
(n 654)] (4)
3.ke
Assume G(fi) < G(fz) without loss of generality. G(fi) = and fi is a constant function because the first eigenvalue of the Laplacian matrix zero. To simplify the equation, we assume without loss of generality. Then:
-()= E ((()))((55)) +n (1t_:///111n.......oo-0-0---0000
(5)
Deep covering options compute the second eigenfunction f by minimizing G(J) instead G(f) (see Algorithm []. Our objective function only needs sampled state-transitions H. instead of
complete state-space graph. As it is an unconstrained optimization problem, we can optimize by simple gradient-based methods. The objective function is essentially the same the objective function of covering options which has theoretical guarantee on the expected cover time but computed approximately that it scales large or infinite state-space domains.
4

---

Published as a conference paper at ICLR 2020
k
Reward
5
2.5311 1.71
10
3.1873 + 3.33
30
3.2210
4.54
50
3.0748
3.28
Table I: The effect of the size of the termination set (percentile k) on the performance of Deep covering options in Pinball with options. Reward is averaged over 100 episodes and runs.
While covering options is constrained to options with the initiation set consisting of single state, we set the termination set as set of states with f value smaller than its k-th percentile. As proposed by Machado et al. (2177; 2018), we define the initiation set to be the complement of the termination set. We train the option policy off-policy, maximizing the total pseudo-reward ro = f(s) - [(s') so that it learns to reach the termination set (i.c., the set of states with f(s) < B²).
4 EXPERIMENTS
We evaluate our method in both the online setting and the setting in which a pretraining phase is available. We use three different platforms: the Pinball domain (Konidaris and Barto (2009). three MuJoCo control tasks (Todorov et al. 2012), and three Atari games (Bellemare al. 2013). See the Appendix for the experimental details.
4.1 OFFLINE OPTION DISCOVERY
We first consider the setting in which the agent collects samples in the environment for given number of time steps before being given a reward signal to maximize.
Pinball In the Pinball domain the goal is to maneuver a small ball from start state to a goal state (Figure 3al Konidaris and Barto 2009). The state-space consists of four continuous variables, the coordinates of the ball position (x: 3/ and the velocity (æ, v). There are five primitive actions: incrementing decrementing & by small amount leaving them unchanged. The ball bounces on colliding with obstacles. In order to reach the goal (red cross) from the initial position (purple circle), the agent must get through one of the narrow passages while taking the bounce into consideration. The agent receives a reward of 10 upon arrival at the goal and of -0.001 in each other time step. The start state is fixed throughout the training.
To generate an option, we sampled 100 trajectories of 1000 time steps which the agent selects between the available actions and options uniformly random. We trained neural network to learn the eigenfunction by minimizing Ô using the sampled state-transitions (see Equation 5). We evaluated with the threshold percentile & (5. 10, 30, 50} and selected 30 as it performed the best (Table I]. We used Q-learning Waakkins and Dayan 1992) with Fourier basis linear function approximation (Konidaris et al., 2011) to train the option policy off-co using the sampled trajectories but using pseudo-reward r. (see Algorithm Tp. We repeat this process with the generated option added to the agent's 's action set.
We evaluate the performance the agent with access the discovered options to evaluate the claim that these options do indeed allow the agent to collect more rewards by making it more capable of navigating through the state space. The agent has access to both these computed options and primitive actions, and uses Q-learning with the Fourier basis to train the high-level policy.
FigureBeedeptin depicts the agent's performance with a varying number of options. The proposed algorithm significantly outperforms the flat baseline. We also evaluated the performance of flat Q-learning pretrained with reward signals for the same number of episodes the hierarchical agents were (base- pretrained). While the options agent with the option set is close to the performance of the agent trained with reward information, showing that such an approach does not hinder performance
generated without reward information, the performance of the
single task setting.
5

---

Published as a conference paper at ICLR 2020
Domains
Offline
Online
Initial position
Septon
Teptice
Septices
Eppede Nenter
Kgewode Dranner
(a) Pinball
(e) Offline (Pinball)
(i) Online (Pinball)
Jarc
goal
Toptas
3:01
2001
000
Movable block
-200
300
Inital position
Ppaval Nomder
Epande Namkerr
(b) PointFall
(f) Offline (PointFall)
(j) Online (PointFall)
2001
26
000
position
130
-00
100
140
00
150
(c) PointMaze
g Offline (PointMaze)
(k) Online (PointMaze)
330
position
2540
800
3001
Avonge Bowal
190
2001
noovabll block
330
2003
(d) PointPush
(h) Offline (PointPush)
(1) Online (PointPush)
Figure 3: Performance of online option discovery agents, averaged over 5 runs. The shaded area shows the standard deviation. In PointFall (Figure (3). the agent must push the movable block into chasm to make bridge that allows it to reach the goal. In PointMaze (Figure [c). the agent must first move away from goal (in terms L2 distance) to successfully reach it, since corridor U-shaped. The green arrow shows successful trajectories. In PointPush (Figure 3d) greedy agent would move forward and push the movable block into the path to reach the goal. To reach the goal, must push movable block the right clear the path towards the goal.

---

Published as a conference paper at ICLR 2020
The termination set generated by deep covering options tend to be larger than options which seek to minimize the size of the termination set (e.g. Harutyunyan et al. 2019). The results indicate that interpretable options are not necessarily efficient for reducing cover time. This is known behavior of option-discovery algorithms based on spectral methods such as eigenoptions (Machado et al. (017).
We also compared our approach to Diversity Is All You Need (DIAYN) (Eysenbach et al. 2019). Like our method, DIAYN was recently proposed to generate exploratory options without using reward signals. While many option discovery methods are limited discrete state-space tasks, DIAYN can operate in continuous control tasks. We trained DIAYN for the same length of pretraining steps (300 episodes each one being 1000 steps long) to generate set of options. See the appendix for details of the agent. While Eysenbach et al. (2019) Section 5.1) assumed that one can pick the option (i.e. skill) with highest reward for the task and trained the agent starting from that single option, we use the more realistic assumption that the agent has no prior information of which option is most useful for given task. Based on this assumption, we evaluated an agent equipped with all the generated options and the primitive actions so that the agent must learn which option is most useful for the given task by itself. We used Q-learning with Fourier basis to train the high-level policy. As the termination condition of DIAYN is not defined by Eysenbach et al. (2019), of 0.0, 0.01, 1.1, and 0.5 for any state, and picked 0. as it performed the best. We set the initiation set to be the whole state space, and evaluated the performance of DIAYN for up to three options. DIAYN outperforms the baseline that consists of only primitive actions. While DIAYN generates diverse set of options by maximizing the mutual information between states and options, it does not consider state connectivity. As our algorithm takes into account the connectivity of the states to generate diverse set of options, it successfully finds an option which leads state close (in terms of the number of steps to reach) to the goal state with high probability, resulting in better performance than DIAYN.
tested the termination probability
MuJoCo Next, we evaluated our method in three simulated continuous control tasks in- troduced by Nachum et al.] (0T8): PointFall, PointMaze, and PointPush. The agent re- ceives a reward signal of value 8000 when it reaches the goal and reward signal of value -(L2 distance to the goal)/ (mll///m possible L2 distance to the goal) otherwise. The agent can- not reach to goal state just by maximizing the immediate reward given by the L2 distance to the goal (see Figure 3. PointFall is difficult for a plain agent because if it just follows the immediate reward it falls off the cliff and can never reach the goal whereas in PointMaze and PointPush are relatively easy for a plain agent as it can eventually reach the goal. The start state is fixed to the same position throughout the training but the initial rotation of the agent is set randomly. We sampled 200 episodes of length 2000 with a uniform random policy to generate each option. We trained the option's 's policy using deep deterministic policy gradient (DDPG Lillicrap et al. 2016). used the same hyperparameters as Wu et al. (2019) for DDPG and for learning the eigenfunction f (Wu et al. 2019 Appendix D2.2), and set the threshold percentile
10.
The high-level policy chooses options with Double Deep Q-learing (van Hasselt et al 2016). We train the agents for 100 episodes, each 2000 time steps long. Figure 3i 3g and 3h show the performance with varying number of options. While the performance improvement is small in PointPush and PointMaze, where even a flat agent can easily reach the goal, it is significantly improved in PointFall, which is hard to solve without an efficient exploration strategy. Our method sometimes even outperforms the agent pretrained with reward signal available (base-pretrained) We trained DIAYN for continuous control tasks too, but it did not outperform the baseline in PointFall, PointMaze, and PointPush. See the Appendix for experimental details.
4.2 ONLINE OPTION GENERATION
In the previous section we evaluated option discovery methods assuming that the agent can collect samples by interacting with the environment prior to solving the task itself. We now evaluate the proposed algorithm in the online setting, where the agent generates options using trajectories sampled during the learning phase. At the beginning of training the agent only has access to primitive actions; it then generates one new option every 2000 time steps using the observed data until the number of options reaches a pre-specified threshold. The option policy is trained off off-policy using the trajectories sampled while training. Thus, our method does not require any extra samples. We use the same learning algorithms and hyperparameters as the offline experiments. These experiments aim to evaluate whether the cost of learning the options when a task is given is prohibitive.
7

---

Published as a conference paper at ICLR 2020
We train the agents for 1000 episodes, each 500 time steps long for Pinball. In the continuous control tasks we train the agents for 200 episodes, each 1000 time steps long. Figure 3i, (right most column) depict the agent's 's performance with a varying maximum number of options. Overall, the proposed algorithm significantly improved performance compared to the baseline in most tasks (i.e., Pinball, PointMaze, and PointFall). As in the previous section, we did not see major improvement in PointPush where the agent can easily discover near-optimal policies using only primitive actions. These results suggest that the proposed method is not only useful for pretraining, but can also discover useful options during training and successfully speed up learning without additional samples.
3j 3k and 31
4.3 QUALITATIVE EVALUATION
We now show how the options discovered in the pretraining phase (see Section improve the agent's 's exploration capabilities. Figure 4a depicts the (z. y) positions visited by the agent in the 10 trajectories generated by a random walk when using only primitive actions. Note that the agent rarely gets through the corridor. Figure 4b visualizes the termination set and one of the trajectories generated by the first option discovered by the algorithm. The shaded region indicates the option termination set. Notice that the algorithm successfully discovers the region under-explored by the agent (Figure 4aj. Figure 4cl shows the (z, y) positions of the states visited by 10 trajectories in total, with 5 trajectories only using primitive actions and 5 trajectories with the first option available to the agent. The agent now consistently gets through the narrow passages. Figure 4d shows one of the trajectories generated by the second discovered option. The same process can be observed when second and third options are added to the action set. They keep identifying under-explored regions of the state space and further narrow down the termination set to visit these regions (Figures 4d). These results suggest that the proposed method successfully extends the frontier of the exploration by discovering options incrementally.
The same intuition holds for continuous control tasks. This can be seen in Figures 4e and 4f Figure 4e shows the states visited by 10 trajectories generated by random walk using primitive actions in PointMaze; the agent does not deviate far from its start state. Figure [4] shows the state visited by 10 trajectories in total, trajectories with primitive actions and 5 with the first option available to the agent; the agent is now able to explore further along the corridor. By incrementally discovering options our method generates options to navigate through the maze without any reward information. This becomes evident in Figure 4g] which depicts the trajectory followed by the first (green), second (yellow), and third (purple) options. Each option explores more deeply into the state space.
To demonstrate the potential of the proposed method in a domain with a very large discrete state-space, we visualize the termination set of options generated in three Atari games from the Arcade Learning Environment (Bellemare et al., 2013): Montezuma's 's Revenge, MsPacman, and Amidar. See the Appendix for the experimental details. The figures suggest that the options aim to visit different regions of the state space, promoting exploration in these games as well. Importantly, unlike other approaches evaluated in Atari games (e.g.. |aacado et al. 2017: 2018), the options our method generates need not to be curated by an expert, who filters out non- non-meaningful options. Nevertheless, further analyses down the eigenspectrum are required for a better understanding of the diversity and utility of the discovered options.
5 CONCLUSION
Deep covering options a new method for learning options to explore the state-space efficiently in a task-agnostic way. By minimizing expected cover time, it automatically discovers less- less-explored regions of the state-space and generates options to reach those regions. Our algorithm is inspired by strong theoretical results in the tabular case while being computationally practical in large domains. We demonstrated the use of our method in a pretraining setting as well as for the traditional online setting. In pretraining experiments we showed that the method is able to generate task-agnostic options which expand the frontier of the known regions of the state space without any reward information and successfully improves the performance of the agent in continuous control tasks. In online experiments we showed that the proposed method can also discover useful options during training and successfully speeds up learning without additional sampling.
8

---

Published as a conference paper at ICLR 2020
C
(a) States visited no options
(b) Trajectory by the 1st option
(c) States visited with 1 option
(d) Trajectory by the 2nd option
(e) States visited with options
(f) States visited with option
(g)
Option trajectories
Option
Option1
Option2
Option2
2393
Option2
Option1
(h)
Montezuma's
Re-
MsPacman
(i) Amidar
venge
Figure 4: Options generated by offline option discovery. (a, f) States visited by random walk without and with options. (b, d) Trajectories obtained by the generated options. Shadowed regions in the figures approximately show the (a. y) coordinate of the termination The ball may not terminate in the shaded region for velocity higher than 0. (g) Trajectories by the first, second, and third option in PointMaze. (h-j) Termination set of the options in Atari games.
when the velocity is O.

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
This research was supported in part by DARPA under agreement number W91 AFOSR Young Investigator Grant agreement number FA9550-11-1-0122.amg the ONR under the PERISCOPE MURI Contract 100014-17-1-266
The U.S. Government is authorized reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The content solely the responsibility of the authors and does not necessarily represent the official views of DARPA, the ONR, or the AFOSR.
REFERENCES
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The Option-Critic architecture. In Proceedings of the Thirty-Fite Phirty-Firstt AAAI Conference on Artificial Intelligence, pages 1726-1734, 2017.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade Learning Environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
Andrei Z Broder and Anna R Karlin. Bounds on the cover time. Journal of Theoretical Probability, (1):101-120, 1989.
Fan RK Chung. Spectral graph theory. American Mathematical Society, 1996.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without reward function. In Proceedings of the Seventh International Conference on Learning Representations, 2019.
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2): 298-305, 1973.
Arpita Ghosh and Stephen Boyd. Growing well-connected graphs. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 6605-6611, 2006.
Jean Harb, Fierre-Luc Bacon, Martin Klissarov, and Doina Precup. When waiting is not option: Learning options with a deliberation cost. In Proceedings of the Thirty-Second AAAI Conference Artificial Intelligence, pages 3165-3172, 2018
Anna Harutyunyan, Will Dabney, Diana Borsa, Nicolas Heess, Remi Munos, and Doina Precup. The termination critic. arXiv preprint 19X2::9902.000 09996, 2019.
Yuu Jinnai, David Abel, D Ellis Hershkowitz, Michael Littman, and George Konidaris. Finding options that minimize planning time. In Proceedingy of the 36th international conference Machine learning, 2019a.
Yuu Jinnai, Jee Won Park, David Abel, and George Konidaris. Discovering options for exploration by minimizing cover time. Proceedings of the 36th International Conference on Machine learning, 2019b.
George Konidaris and Andrew Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. In Proceedings of the 22nd Conference on Advances in Neural Information Processing Systems, pages 1015-1023, 2009.
George Konidaris, Sarah Osentoski, and Philip Thomas. Value function approximation in reinforce- ment learning using the Fourier basis. In Proceedings of the Twenty-fifth AAAI conference on Artificial Intelligence, 2011.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Brez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Fourth International Conference on Learning Representations, 2016.
Marlos C. Machado and Michael Bowling Learning Purposeful Behaviour in the Absence of Rewards. In ICML-16 Workshop Abstraction Reinforcement Learning, 2016.
10

---

Published as a conference paper at ICLR 2020
Marlos C Machado, Mare G Bellemare, and Michael Bowling. A Laplacian framework for option discovery in reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pages
2017.
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In Proceedings of the Sixth International Conference on Learning Representations, 2018.
Daniel Mankowitz, Timothy A Mann, and Shie Mannor. Adaptive skills adaptive partitions (ASAP). In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1588-1596, 2016.
Amy McGovern and Andrew Barto. Automatic discovery of subgoals reinforcement learning using diverse density. In Proceedings of the 18th International Conference Machine Learning. pages 361-368 2001.
Ishai Menache, Shie Mannor, and Nahum Shimkin. Q-cut dynamic discovery of sub-goals in reinforcement learning. In Proceedings of the 13th European Conference on Machine Learning. pages 295-306 2002.
Ofir Nachum, Shixiang Shane Gu, Honglak Lec, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3303-33 3313,, 2018.
Özgür Şimşek and Andrew G Barto. Using relative novelty to identify useful temporal abstractions in reinforcement learning. In Proceedings of the Twenty-Firs International Conference on Machine learning, pages 95-102, 2004.
Örgür Şimşek and Andrew G Barto. Skill characterization based on betweenness. In Proceedings of the Advances in Neural Information Processing Systems, pages 1497-1504, 2009.
Özgür Şimşek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd international conference on Machine learming, pages 81 816-823, 2005.
Martin Stolle and Doina Precup. Learning options in reinforcement learning. In International Symposium on abstraction, reformulation, and approximation, pages 212-2233 2002.
2002.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction reinforcement learning. Artificial Intelligence. 12(11)181-211, 1999.
Saket Tiwari and Philip S Thomas. Natural option critic. In Proceedings of the Thirty-Thirl Conference Artificial Intelligence, 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. MuloCo: physics engine for model-basee control. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033, 2012.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. In Proceedings of the Thirtieth AAAI Conference Artificial Intelligence, 2016.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, ((3):279-292, 1992.
Yifan Wu, George Tucker, and Ofir Nachum. The Laplacian in RL: Learning representations with efficient approximations. In Proceedings of the Seventh International Conference on Learning Representations, 2019.
11

---

Published as a conference paper at ICLR 2020
A EXPERIMENTAL SETUP
A.1 PINBALL
We used Q-learning (a 0 0.99. 0.05) with linear function approximation with 3rd-order Fourier basis Konidaris et al. (2011) to train the policy of the option off- using the sampled trajectories but using the intrinsic reward r, (Algorithm 1). We set the percentile to k 30. We set the Lagrange multiplier to 1.0.
We used Q-learning (a- 0.1, 0.99, 0.05) with 3rd-order Fourier basis to train the high-level policy. The option's 's policy is obtained with Qllaarnin (a = 0.1, = 0.99, = 0.05) with linear function approximation with 3rd-order Fourier basis. We used the same setup for both offline and online option discovery.
A.1.1 DIAYN
The actor and the critic are implemented with 3 hidden layers with 256 units each followed by a ReLU activation function with Adam optimizer with a step size of 0.005. We used neural networks for the actor and the critic as it outperformed an agent with the actor and the critic implemented by a linear approximator using 3rd order Fourier basis Konidaris al. (201T). Our discriminator network consists of 2 hidden layers with 256 units each followed by a ReLU activation function. We trained the discriminator with Adam optimizer with step size of 0.001.
We used Q-learning (a = 0.1, 7 = 0.99, c = 0.05) with linear function approximation with 3rd-order Fourier basis to train the high-level policy. As the termination condition of DIAYN is not defined in the work by [Esenbbahh et al. (2019), we tested the termination probability of 0.0, 0.01, and 0.1, and 0.5 for any states. We picked 0.1 performed the best.
A.2 MuJoCo
We trained the option's 's policy using deep deterministic policy gradient Lillicrap et al. (016). We used the same hyperparameters as Wu al. (2019) for DDPG and the eigenfunction f (see Appendix D.2.2 in Wu et al. (2019)). We set the threshold percentile k = 10. We set the Lagrange multiplier to 1.0.
The high-level policy chooses options with double deep Q-learning van Hasselt et al. (2016). The Q-network consists of two fully connected layers with 400 units with a batch normalization and a ReI.U in between. We trained it with the Adam optimizer using step size of 0.0001 and batch size of 64. We updated a target policy every step by update rate of 0.001. We set e to 0.05. We used the same setup for both offline and online option discovery.
We evaluated DIAYN for the continuous control tasks. The actor and the critic consist of three hidden layers with 256 units each followed by ReLU activation function with Adam optimizer with step size of 0.005. Our discriminator network consists of two hidden layers with 256 units each followed by ReL.U activation function. We evaluated Adam optimizer with a step size of 0.001 and 0.005 for the discriminator. We used double DQN van Hasselt et al. (2016) to implement the high-level policy. The Q-network consists of three fully connected layers with 400 units with batch normalization and a ReLU in between. We also evaluated the Q-network with two fully connected layers. We trained it with the Adam optimizer with step size of 0.001 and a batch size of 64. We updated a target policy every step by update rate of 0.001. We also tried update rate of 0.01. For the setup we have tried, DIAYN did not outperform the baseline in all PointMaze, PointPush, and PointFall.
A.3 ARCADE LEARNING ENVIRONMENT
We use the screen image as the observation and train f using the sampled pixel images. We use a transformation from the original (210, 160, 3) dimensional RGB image to (105, 80) grayscale image. We set the threshold percentile & 4. We set the Lagrange multiplier 7 to 1.0. We sampled 200 trajectories each being 2000 steps long. The eigenfunction is learned with a convolutional neural network with 2 convolution layers (32 8x8 filters with stride 4 and 64 4x4 filters with stride 2) and fully-connected hidden layer with 400 units and ReLU in between. We trained the policy of the option with double deep Q-learnig van Hasselt et al. (016)). The Q-network consists of 2 convolution
12

---

Published as a conference paper at ICLR 2020
layers (32 8x8 filters with stride 4 and 64 4x4 filters with stride 2) and fully-connected hidden layer with 400 units and ReLU in between. We trained it with Adam optimizer with a step size of 0.0001 and batch size of 64. We updated target policy every step by update rate of 0.001. We set e to 0.05. We sampled 50 trajectories and plotted the positions of the player agent when the option terminated. The plots depict the termination of the generated options. The figures suggest that different options aim at visiting different regions of the state space, promoting exploration in these games well. Importantly differently from other approaches evaluated in Atari games (e.g.. Machado et al. 2 2018), the options our method generates do not need to be curated by an expert, with the first eigenfunctions being able to generate meaningful options. Nevertheless, further analyses down the eigenspectrum are required for a better understanding of the diversity and utility of the discovered options.
13


Reviews:
[{"review_id": "HJlGfUk0KH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe authors introduce deep covering options, an online mechanism to extend the covering options to large state spaces. They claim their method discovers options that are task agnostic. The method is evaluated in sparse reward domains and claims to gain improvement in exploration and performance as well.  The authors extend the recent developments in eigenfunction estimation of the Laplacian to a principled approach for option discovery to non-linear function approximation. \n\nCovering options compute the second smallest eigenvalue and the corresponding eigenvector f of the Laplacian exactly by solving a constrained optimization problem (Eq2). However, this requires the adjacency matrix A as input, and a constrained optimization problem is hard to solve using gradient-based methods. To overcome this, the authors propose an approximation of the computation of the Laplacian with Eq3. This allows them to have a constraint-free objective to compute the eigenfunction which is now dependent on the trajectories and avoids requiring the state-space graph. I believe the paper presents interesting ideas and is definitely a very useful contribution.  However, the paper needs work on thorough empirical analysis: could use more rigorous baselines especially to fairly evaluate the gains in exploration. \n\nDetailed comments:\n(I) Major Concern:  Figure 1 of this work is exactly the same as Figure 2 of the Jinnai et al., 2019b. It is not clear to me whether a) this is being referred for the purpose of giving intuitions. If yes, then it should be cited as Figure from Jinnai et al., 2019b or b) this is a new figure generated differently, it is not clear what the difference is. Overall, there is overlapping content and should be clarified what is original work and what is being referred to. \n\nReusing content from another paper without proper attribution is normally considered plagiarism. More precisely; Jinnai et al., 2019b. mention that the “second smallest eigenvalue of L is known as the algebraic connectivity of the graph and its corresponding eigenvector is called Fiedler vector” and caption this figure:\n“Figure 2: The distance between the red state and all other states, measured via the Fiedler vector (left) and Euclidean distance (right). The Fiedler vector captures the connectivity of the graph, so distances measured using it reflect path lengths in the graph; the pair of nodes with the maximum and the minimum value are the farthest apart” \nThis  work (currently in review) captions this figure as: \n“Figure 1: The distance between the red state and all other states, measured via the second eigenvector (left) and Euclidean distance (right). The second eigenvector captures the connectivity of the graph, so distances reflect path lengths in the graph; the pair of nodes with the maximum and minimum values are the farthest apart.” The only words changed are Fiedler vector to the second eigenvector. Please explain!\n\n(II) An important step in the algorithm is line 3” identify an under-explored region in the state-space using the eigenfunctions”. Where does the parameter k come from? Is this a hand-designed parameter such as in PinBall it is somehow set to 30, for Mujoco tasks this is somehow set to 10, and for Atari, this is set to 4.  Would it be possible to comment on the hyperparameter threshold percentile k? Why is this a hard-coded choice? Would it be possible to learn this *simultaneously* as the options? \n\n(III) Can you comment on to what extent do you see theoretical guarantees of covering options apply to the function approximation case as they no longer hold when going from tabular setting to the nonlinear function approximation? Would it be possible to also comment on what can be said about any guarantees at all if the state space is very very large? Forex: imagine a lifelong learning scenario where the environment is really big, and it is just not almost impossible to visit all states, how does this objective function of minimizing the upper bound on the expected cover time constitute the right choice? \n\n(IV) Intuitively the pseudo-reward seems a lot related to goal-based rewards, where the skill is learned to reach different goals such as in DIAYN. Can you comment on how is this different and why is the proposed approach better in principle?\n Empirically, It is not clear why DIAYN was not compared as it is and with all the stated modifications.  In DIAYN, setting the initiation set to be the whole state space seems counterintuitive. \n\n(V) Regarding the connectivity of the states to generate a diverse set of options: there seem to be connections to the work on constructing options using stronger guarantees Castro & Precup, 2011. It might be useful to comment on this and discuss this in the paper.\n\n(VI) “We sampled 200 episodes of length 2000 with a uniform random policy to generate each option.” Would there be smarter ways to generate each option? Is there a reason to generate each option in this fashion?\n\n(VII) Since the idea here is to connect states that are closer in terms of time, but further apart, how does the proposed approach comparison to successor options. I would imagine a comparison to successor options would be quite valuable to this. Please comment on this. \n\n(VIII) “Termination set generated by deep covering options tends to be larger than..” Intuitively speaking, it is not clear why this is a good idea. Wouldn't we want the options to be peaked in places they terminate and initiate in, and therefore have smaller termination/initiation set? \n\n(IX) In the Mujoco tasks: I would expect to see the baseline performance reported in the main paper i.e. DIAYN for continuous control tasks too. It is not clear by “did not outperform the baseline” as to how the proposed approach fairs in comparison to DIAYN. Looking into the appendix, It is still not clear why the plot of DIAYN in mujoco tasks is not included. \nSince the key ideas in this work propose overcoming exploration as the main challenge, one would expect a comparison to the state-of-art in exploration, for instance [1]. Also since the work builds on eigenoptions, it would help compare with [2] as well. Without these comparisons, I find the empirical analysis rather weak. \n\n(X) Pinball exploration visuals show concrete gains in state-space explored 4a-d. This is also evident in continuous control tasks 4e-f-g. However, in both cases, I find the comparison weak as the authors do not compare against state-of-the-art exploration baselines.  \n\n(XI)  The termination sets in ALE are interesting in that they do convey that options terminate in different regions of the state space: but one can also see options terminating in different regions of the state space in Harb et al, 2018 in Amidar here for example. It is also counter-intuitive as to why the options terminate in regions that do not overlap with visible goals for example in Montezuma Revenge in the key or skull. Perhaps one benefit here is that there is no reward information, but we do not see either the performance curve or the nature of options in ALE, so it is really hard to make a strong claim either way.\n\nAlthough the options in pre-training were generated without a reward- I would recommend using these options in different tasks to make the claim “task agnostic options are discovered” much stronger. \n[1] Count-based exploration with the successor representation.\n[2] A laplacian framework for option discovery in reinforcement learning\n\nOverall\nScales a principled approach to function approximation for deep covering options. The method seems to be computationally tractable. The approach can be applied to both settings where an unsupervised pre-training phase is available and also in a fully online setting.\n\nHowever, DIAYN is the only baseline in Mujoco and is not shown. It’s unclear why other baselines were not used such as Eigenoptions, which seems like a very valid baseline. In addition, baselines of well-known exploration algorithms also have not been fully explored. The paper needs a more thorough evaluation of the proposed method to make the claims stronger.\n\nPlease note that although I have marked a weak reject, I am open to adjusting my score if the rebuttal addresses enough issues. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byx79-ee9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an algorithm to extend the recently proposed method of “covering options” from a tabular setting to continuous state spaces (or large discrete state spaces). The proposed algorithm approximately computes the second eigenfunction of the normalized laplacian of the state space, uses it to identify an under-explored region and trains an option to terminate in such a region. Each new learnt option is added to the initial set of primitive actions and a policy over this growing set of actions is learnt separately. An online algorithm is also proposed that does the above option learning process intermittently in addition to training for an external task. The paper shows empirical evidence of better or equal performance to base algorithms which do not discover options, prior work such as DIAYN (Eysenbach et. al, 2019) (that discover options via mutual information maximization between visited states and options), as well as ablations of their proposed method with different number of options.\n\nI vote for weak reject due to (1) the idea of covering options (Jinnai et. al., 2019b) and the approximation for the graph laplacian (Wu et. al., 2019) both have been shown in prior work and the novelty in this paper seems to be limited to putting together these two ideas, and (2) the paper shows quantitative results for options discovered for simple environments whereas only qualitative options are shown for harder exploration tasks, and (3) given that exploration is a key problem being addressed, a comparison to other exploration algorithms which are non-option based methods has not been shown -- which makes for a weak argument for using an option-based method for exploration as opposed to existing methods for exploration.\n\nOther comments:\n- The paper does a good job at explaining covering options, the approximations involved in their algorithm and how options can be learnt with the help of such approximations. It makes sense that an algorithm that takes into account state connectivity will do better than DIAYN (Eysenbach et. al., 2019) which just promotes diversity of visited states across options. \n\n- The paper made some assumptions on the implementation of DIAYN, citing lack of details in Eysenbach et. al (2019). Were these details not available in the code released by DIAYN on their project page? (I’m not sure if I should post the link here, but it is easy to find). I have some concern that a fair comparison may not have been made due to the paper’s implementation of this baseline, but I am also not sure how important of a comparison this is given that their method for discovering options is quite different. I would argue that DIAYN is different enough that the proposed method deserves comparisons with methods for exploration that do not use options.\n\n- In the intro, “...extend a theoretically principled approach for option discovery to the non-linear function approximation case” seems to be highly misleading, since it suggests that the theoretical guarantees are extended, which is not the case in this paper as the approximations have no states guarantees.\n\nThe proposed method seems to have the potential to be a good at exploration but the paper does not show quantitative experiments for hard exploration tasks such as Montezuma’s Revenge, or other Atari ALE environments. I am curious to see how many levels of Montezuma’s revenge can be covered by simply applying deep covering options to it.\n\nReferences:\nAll references are same as the paper.\n\nAfter rebuttal: The authors have addressed most major concerns and I am increasing my score to weak accept.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BygSuR-qFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes deep covering options. This method extends laplacian based option generation techniques to continuous domains. The resulting options are task independent and enable efficient exploration. The method can be applied in continuous state (and action) domains and options can be learnt in an online manner.\n\nI favour acceptance of this paper. While the method seems to be mostly a combination of the ideas in 2 referenced previous works, the method seems to work well in a diverse set of circumstances.\n\nDetailed comments: \n\n-The proposed method seems mainly a combination of covering options with the techniques from (Wu et al.) to compute the eigenfunctions. As such it could be argued  to the core ideas in the paper aren’t very novel. Nonetheless, I found the approach interesting. Moreover, it is interesting to see an option generation technique that applies to such a wide range of problems.\n\n-The paper gives a broad overview of related work and situates the method with respect to previous option generation methods. The background given on the laplacian, its eigenfunctions and their properties was short to the point of not being very clear. The algorithms are given without much context. I found myself referring to the earlier papers for a more thorough explanation of the core ideas. I would suggest shortening the other sections somewhat in favour of a more intuitive and self contained explanation.\n\n- The effectiveness of the method is demonstrated on a set of very diverse problems that go well beyond the traditional grid worlds often used in option literature. The method is also compared to another unsupervised option generation method.\n\n- It is interesting to see a method that can incrementally grow the set of options while learning, without any pre-training or requiring additional samples. This has the potential to have a large impact on large scale learning approaches\n\n- What is the cost of repeatedly solving the minimization problem in (5)?\n\nMinor comments:\n\n- For several experiments the reward curve starts out high or rapidly becomes high and then decreases during learning. Can the authors explain this odd behaviour? This seems to mainly happen with the option methods in the continuous control domains\n\n- Why are there no learning curves for the ATARI domain?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers options discovery in hierarchical reinforcement learning. It extends the idea of covering options, using the Laplacian of the state space discover a set of options that reduce the upper bound of the environment's cover time, to continuous and large state spaces. An online method is also included, and evaluated on several domains.

The reviewers had major questions on a number of aspects of the paper, including around the novelty of the work which seemed limited, the quantitative results in the ATARI environments, and problems with comparisons to other exploration methods. These were all appropriately dealt with in the rebuttals, leaving this paper worthy of acceptance.
Decision: Accept (Poster)