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.
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.