Title: EXPLORATION IN REINFORCEMENT LEARNING WITH DEEP COVERING OPTIONS

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. However, 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 taskagnostic 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.

1. 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., 2002; Stolle and Precup, 2002; Şimşek and Barto, 2004; Şimşek et al., 2005; Şimşek and Barto, 2009; Machado et al., 2017; Eysenbach 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 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 we show how recent developments in eigenfunction estimation of the Laplacian (Wu et al., 2019) can be used to extend a principled approach for option discovery (Jinnai et al., 2019b) 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 in 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 a wide range of domains. First, we apply it to the Pinball domain (Konidaris and Barto, 2009) , which has a discrete action-space and a continuous state-space. Second, we apply it to three MuJoCo control tasks (Todorov et al., 2012) , which are continuous state-and action-space domains. In all of these domains, our method improves over the baseline. Finally, we perform a qualitative analysis of our method in three Atari 2600 games (Bellemare et al., 2013) 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.

2. BACKGROUND AND RELATED WORK:

We assume the standard reinforcement learning setting (Sutton and Barto, 1998) , where the environment is modeled as a Markov Decision Process (MDP), (S, A, T, R, γ), where S is the set of states, A is the set of actions, T : S × A × S → [0, 1] is the state transition function, R : S × A → R is the reward function, and 0 ≤ γ ≤ 1 is the discount factor.

We use the options framework (Sutton et al., 1999) to represent temporally extended actions. It defines an option as a triple (I, π, β), where I ⊆ S is the set of states in which the option can initiate, π : S → Pr(A) is the policy the agent follows when that option is being executed, and β : S → [0, 1], is the termination condition. We refer to a set of states in which β(s) = 1 as a 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 (e.g., Mankowitz et al., 2016; Bacon et al., 2017; Harb et al., 2018; Tiwari and Thomas, 2019) . These approaches are often ineffective in sparse reward problems, where only a few state-action pairs lead to a positive reward.

Fewer papers have tackled the problem of option discovery for exploration without using reward signals. Eysenbach et al. (2019) proposed to generate options maximizing an 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 reward function. Machado et al.; Machado et al. (2017; 2018) proposed eigenoptions, a 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 a 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., 2005) , visitation statistics ( Şimşek and Barto, 2004; Stolle and Precup, 2002) , and betweenness centrality ( Şimşek and Barto, 2009) . As they use graph algorithms to discover subgoals, their scope is 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 a uniformly random policy by augmenting the agent's action set 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 a random walk is going to lead to a 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, λ 2 , also known as the algebraic connectivity (Fiedler, 1973) :

EQUATION

where n is the number of vertices of the graph. Equation 1shows 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 to λ 2 is an embedding of a graph to a one-dimensional interval where nodes connected by an edge tend to be placed nearby (see Figure 1 , adapted from Jinnai et al., 2019b) . A pair of nodes with the maximum and minimum value in f are 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 as follows:

1. Compute the second smallest eigenvalue and the corresponding eigenvector f of the Laplacian exactly by solving the following constraint optimization problem:

EQUATION

where A is the adjacency matrix of the state-space graph where the entry at (s, s ) is 1 if s and s are adjacent and 0 otherwise.

2. Let v i and v j be the state with largest and smallest value in the eigenvector respectively. Generate two options; one with I = {v i } and β = {v j } and the other one with I = {v j } and β = {v i }. Each option policy is the optimal path from the initial state to the termination state.

3. Set G ← G ∪ {(v i , v j )} and repeat the process until the number of options reaches a threshold.

While this method is an efficient algorithm with performance guarantees, it is limited to small discrete MDPs as it requires a state-space graph. Moreover, explicitly computing the matrix that encodes the environment's adjacency matrix is 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 a single state. This is not useful for tasks with large (or continuous) state-spaces as the probability of visiting the state in the initiation set of the option tends to zero. Even if the agent visits the state in the option's initiation set and starts following the corresponding option's policy, the probability of reaching the state in the termination set is also small (see Figure 2 ). In the next section we introduce an approach that addresses these limitations.

3. 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 a 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 1):

Algorithm 1 Deep covering options 1: Input: Set of state-transitions H, a percentile 0 ≤ k ≤ 100 2: Compute f by minimizing G(f ) using H (Equation 5)

3: β ← k-th percentile value of f in H 4: β o (s) ← 1 if f (s) < β 0 otherwise 5: I o ← {s|β o (s) = 0, s ∈ S} 6:

Train π o off-policy by maximizing the total accumulated pseudo-rewards

r o = f (s) -f (s ) using H and f 7: Return (I o , π o , β o )

1. compute an eigenfunction of the Laplacian of the state-space graph approximately (line 2 in Algorithm 1), 2. identify an under-explored region in the state-space using the eigenfunctions (line 3), 3. set the under-explored region as the termination set and set the compliment of it as the initiation set (line 4, 5), 4. train a policy of the option using the pseudo-reward induced by the eigenfunctions (line 6).

There are two problems in Equation 2 that prevent its applicability to non-tabular domains. First, the equation requires the adjacency matrix A as input. Second, a constrained optimization problem is hard to solve using gradient-based methods. We address these issues by approximating the computation of the Laplacian with the following objective (Wu et al., 2019, Equation 6):

EQUATION

)

where H is the set of sampled state-transitions, ρ is a distribution of states in the dataset (ρ(s) is the number of occurrence of s in H divided by the size of H), η is the Lagrange multiplier, and δ jk is 1 if j = k and 0 otherwise. Such an expression, inspired by spectral graph drawing theory, uses the repulsive term (the summation multiplied by η) to ensure the functions f 1 , ..., f d are orthogonal to each other. Unlike G, G is a constraint-free objective to compute the eigenfunction, only requiring trajectories instead of the state-space graph.

As we only require the second eigenfunction (unlike eigenoptions), we can simplify the objective function to take only two arguments:

EQUATION

Assume G(f 1 ) ≤ G(f 2 ) without loss of generality. G(f 1 ) = 0 and f 1 is a constant function because the first eigenvalue of the Laplacian matrix is zero. To simplify the equation, we assume f 1 = 1 without loss of generality. Then:

G(f ) = G(1, f ) = 1 2 E (s,s )∼H f (s)-f (s ) 2 +ηE s∼ρ,s ∼ρ f (s) 2 -1 f (s ) 2 -1 +f (s) 2 f (s ) 2 .

(5) Deep covering options compute the second eigenfunction f by minimizing G(f ) instead of G(f ) (see Algorithm 1). Our objective function only needs sampled state-transitions H instead of a 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 as the objective function of covering options which has theoretical guarantee on the expected cover time but computed approximately so that it scales to large or infinite state-space domains.

k Reward 5 2.5311 ± 1.71 10 3.1873 ± 3.33 30 3.2210 ± 4.54 50 3.0748 ± 3.28

Table 1 : The effect of the size of the termination set (percentile k) on the performance of Deep covering options in Pinball with 3 options. Reward is averaged over 100 episodes and 5 runs.

While covering options is constrained to options with the initiation set consisting of a single state, we set the termination set as a set of states with f value smaller than its k-th percentile. As proposed by Machado et al. (2017; 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 r o = f (s)f (s ) so that it learns to reach the termination set (i.e., the set of states with f (s) < β ).

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 et 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 a 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 a start state to a goal state (Figure 3a ; Konidaris and Barto, 2009) . The state-space consists of four continuous variables, the coordinates of the ball position (x, y) and the velocity ( ẋ, ẏ). There are five primitive actions: incrementing or decrementing ẋ or ẏ by a small amount or 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 in which the agent selects between the available actions and options uniformly at random. We trained a neural network to learn the eigenfunction by minimizing G using the sampled state-transitions (see Equation 5). We evaluated with the threshold percentile k = {5, 10, 30, 50} and selected 30 as it performed the best (Table 1 ). We used Q-learning (Watkins and Dayan, 1992) with Fourier basis linear function approximation (Konidaris et al., 2011) to train the option policy off-policy using the sampled trajectories but using the pseudo-reward r o (see Algorithm 1). We repeat this process with the generated option added to the agent's action set.

We evaluate the performance of the agent with access to 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.

Figure 3e 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 (basepretrained). While the options are generated without reward information, the performance of the 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 even in a single task setting. (l) Online (PointPush)

Domains:

Figure 3 : Performance of online option discovery agents, averaged over 5 runs. The shaded area shows the standard deviation. In PointFall (Figure 3b ), the agent must push the movable block into a chasm to make a bridge that allows it to reach the goal. In PointMaze (Figure 3c ), the agent must first move away from the goal (in terms of L2 distance) to successfully reach it, since the corridor is U-shaped. The green arrow shows successful trajectories. In PointPush (Figure 3d ) a greedy agent would move forward and push the movable block into the path to reach the goal. To reach the goal, it must push a movable block to the right to clear the path towards the goal.

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 a known behavior of option-discovery algorithms based on spectral methods such as eigenoptions (Machado et al., 2017) .

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 to 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 a 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 a 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) , we tested the termination probability of 0.0, 0.01, 0.1, and 0.5 for any state, and picked 0.1 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 a 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 to a state close (in terms of the number of steps to reach) to the goal state with high probability, resulting in better performance than DIAYN.

MuJoCo Next, we evaluated our method in three simulated continuous control tasks introduced by Nachum et al. (2018) : PointFall, PointMaze, and PointPush. The agent receives a reward signal of value 8000 when it reaches the goal and a reward signal of value -(L2 distance to the goal)/(maximum possible L2 distance to the goal) otherwise. The agent cannot 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 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 k = 10.

The high-level policy chooses options with Double Deep Q-learning (van Hasselt et al., 2016) . We train the agents for 100 episodes, each 2000 time steps long. Figure 3f , 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-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.

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 , 3j, 3k, and 3l (right most column) depict the agent'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 a 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.

4.3. QUALITATIVE EVALUATION:

We now show how the options discovered in the pretraining phase (see Section 4.1) improve the agent's exploration capabilities. Figure 4a depicts the (x, 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 4a ). Figure 4c shows the (x, 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 a 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 a random walk using primitive actions in PointMaze; the agent does not deviate far from its start state. Figure 4f shows the state visited by 10 trajectories in total, 5 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 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., Machado et al., 2017; 2018) , the options our method generates need not to be curated by an expert, who filters out 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 is 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-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. layers (32 8x8 filters with stride 4 and 64 4x4 filters with stride 2) and a 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 a batch size of 64. We updated a target policy every step by update rate of 0.001. We set to 0.05. We sampled 50 trajectories and plotted the positions of the player agent when the option terminated. The plots depict the termination set of the generated options. The figures suggest that different options aim at visiting different regions of the state space, promoting exploration in these games as well. Importantly, differently from other approaches evaluated in Atari games (e.g., Machado et al., 2017; 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.

:



Figures and Tables:

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. Figure is adapted from Jinnai et al. (2019b), Figure 2.

Figure 2: Comparison between options generated 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 a single state, making them impractical in large state-spaces.

(a) States visited with no options (b) Trajectory by the 1st option (c) States visited with 1 option (d) Trajectory by the 2nd option (e) States visited with no options (f) States visited with 1 option (g

Figure 4: Options generated by offline option discovery. (a, c, e, f) States visited by a random walk without and with options. (b, d) Trajectories obtained by the generated options. Shadowed regions in the figures approximately show the (x, y) coordinate of the termination set when the velocity is 0. 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.

Peer review (iclr2020):
Summary The 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. Covering 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. Detailed comments: (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. Reusing 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: “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” This work (currently in review) captions this figure as: “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! (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? (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? (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? 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. (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. (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? (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. (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? (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. Since 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. (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. (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. Although 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. [1] Count-based exploration with the successor representation. [2] A laplacian framework for option discovery in reinforcement learning Overall Scales 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. However, 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. Please note that although I have marked a weak reject, I am open to adjusting my score if the rebuttal addresses enough issues.