EIGENOPTION DISCOVERY THROUGH THE DEEP SUCCESSOR REPRESENTATION
Options in reinforcement learning allow agents to hierarchically decompose a task into subtasks, having the potential to speed up learning and planning. However, autonomously learning effective sets of options is still a major challenge in the field. In this paper we focus on the recently introduced idea of using representation learning methods to guide the option discovery process. Specifically, we look at eigenoptions, options obtained from representations that encode diffusive information flow in the environment. We extend the existing algorithms for eigenoption discovery to settings with stochastic transitions and in which handcrafted features are not available. We propose an algorithm that discovers eigenoptions while learning non-linear state representations from raw pixels. It exploits recent successes in the deep reinforcement learning literature and the equivalence between proto-value functions and the successor representation. We use traditional tabular domains to provide intuition about our approach and Atari 2600 games to demonstrate its potential.
Eigenoption Discovery Through the Deep Successor Representation
The paper is a follow up on previous work by Machado et al. (2017) showing how proto-value functions (PVFs) can be used to define options called “eigenoptions”. In essence, Machado et al. (2017) showed that, in the tabular case, if you interpret the difference between PVFs as pseudo-rewards you end up with useful options. They also showed how to extend this idea to the linear case: one replaces the Laplacian normally used to build PVFs with a matrix formed by sampling differences phi(s') - phi(s), where phi are features. The authors of the current submission extend the approach above in two ways: they show how to deal with stochastic dynamics and how to replace a linear model with a nonlinear one. Interestingly, the way they do so is through the successor representation (SR). Stachenfeld et al. (2014) have showed that PVFs can be obtained as a linear transformation of the eigenvectors of the matrix formed by stacking all SRs of an MDP. Thus, if we have the SR matrix we can replace the Laplacian mentioned above. This provides benefits already in the tabular case, since SRs naturally extend to domains with stochastic dynamics. On top of that, one can apply a trick similar to the one used in the linear case --that is,  construct the matrix representing the diffusion model by simply stacking samples of the SRs. Thus, if we can learn the SRs, we can extend the proposed approach to the nonlinear case. The authors propose to do so by having a deep neural network similar to Kulkarni et al. (2016)'s Deep Successor Representation. The main difference is that, instead of using an auto-encoder, they learn features phi(s) such that the next state s' can be recovered from it (they argue that this way psi(s) will retain information about aspects of the environment the agent has control over).
This is a well-written paper with interesting (and potentially useful) insights. I only have a few comments regarding some aspects of the paper that could perhaps be improved, such as the way eigenoptions are evaluated.
One question left open by the paper is the strategy used to collect data in order to compute the diffusion model (and thus the options). In order to populate the matrix that will eventually give rise to the PVFs the agent must collect transitions. The way the authors propose to do it is to have the agent follow a random policy. So, in order to have options that lead to more direct, "purposeful" behaviour, the agent must first wander around in a random, purposeless, way, and hope that this will lead to a reasonable exploration of the state space. 
This problem is not specific to the proposed approach, though: in fact, any method to build options will have to resolve the same issue. One related point that is perhaps more specific to this particular work is the strategy used to evaluate the options built: the diffusion time, or the expected number of steps between any two states of an MDP when following a random walk. First, although this metric makes intuitive sense, it is unclear to me how much it reflects control performance, which is what we ultimately care about. Perhaps more important, measuring performance using the same policy used to build the options (the random policy) seems somewhat unsatisfactory to me. To see why, suppose that the options were constructed based on data collected by a non-random policy that only visits a subspace of the state space. In this case it seems likely that the decrease in the diffusion time would not be as apparent as in the experiments of the paper. Conversely, if the diffusion time were measured under another policy, it also seems likely that options built with a random policy would not perform so well (assuming that the state space is reasonably large to make an exhaustive exploration infeasible). More generally, we want options built under a given policy to reduce the diffusion time of other policies (preferably ones that lead to good control performance).
Another point associated with the evaluation of the proposed approach is the method used to qualitatively assess options in the Atari experiments described in Section 4.2. In the last paragraph of page 7 the authors mention that eigenoptions are more effective in reducing the diffusion time than “random options” built based on randomly selected sub-goals. However, looking at Figure 4, the terminal states of the eigenoptions look a bit like randomly-selected  sub-goals. This is especially true when we note that only a subset of the options are shown: given enough random options, it should be possible to select a subset of them that are reasonably spread across the state space as well. 
Interestingly, one aspect of the proposed approach that seems to indeed be an improvement over random options is made visible by a strategy used by the authors to circumvent computational constraints. As explained in the second paragraph of page 8, instead of learning policies to maximize the pseudo-rewards associated with eigenoptions the authors used a myopic policy that only looks one step ahead (which is the same as having a policy learned with a discount factor of zero). The fact that these myopic policies are able to navigate to specific locations and stay there suggests that the proposed approach gives rise to dense pseudo-rewards that are very informative. As a comparison, when we define a random sub-goal the resulting reward is a very sparse signal that would almost certainly not give rise to useful myopic policies. Therefore, one could argue that the proposed approach not only generate useful options, it also gives rise to dense pseudo-rewards that make it easier to build the policies associated with them.