The problem of exploration in reinforcement learning is well-understood in the tabular case and many sample-efficient algorithms are known. Nevertheless, it is often unclear how the algorithms in the tabular setting can be extended to tasks with large state-spaces where generalization is required. Recent promising developments generally depend on problem-specific density models or handcrafted features. In this paper we introduce a simple approach for exploration that allows us to develop theoretically justified algorithms in the tabular case but that also give us intuitions for new algorithms applicable to settings where function approximation is required. Our approach and its underlying theory is based on the substochastic successor representation, a concept we develop here. While the traditional successor representation is a representation that defines state generalization by the similarity of successor states, the substochastic successor representation is also able to implicitly count the number of times each state (or feature) has been observed. This extension connects two until now disjoint areas of research. We show in traditional tabular domains (RiverSwim and SixArms) that our algorithm empirically performs as well as other sample-efficient algorithms. We then describe a deep reinforcement learning algorithm inspired by these ideas and show that it matches the performance of recent pseudo-count-based methods in hard exploration Atari 2600 games.
Being familiar but not an expert in reinforcement learning, my review will focus on the overall soundness of the proposed method
Summary:
The authors are interested in the problem of sample efficiency in reinforcement learning, i.e. how to learn a policy achieving good performance (discounted reward) in a RL setting using as little interaction with the environment as possible.
To do this the authors propose to learn a policy in a new environment where the reward has changed: an exploration bonus is added to the reward that should bias the agent towards the least frequently visited states.
The algorithms proposed throughout the manuscript are extensions of a two-part algorithm of the following flavour: 1) An estimate of visitation count is done in an online fashion using a modified version of the successor representation (SR). 2) This estimates parametrizes the exploration bonus of the environment . Both learning algorithms are optimized together.
This initial algorithm is fairly simple in its description and builds on well established ideas in RL. The authors then ‘evaluate the effectiveness of the proposed exploration bonus in a standard model-based algorithm’ against other baselines. They do explain how the model is learned, but not how the policy is optimized.
The remainder of the manuscript applies the same idea to different settings.
For large state spaces, The SR expected visits are learned using TD along with state action value functions. The counts of visitations are replaced by features that are also learned.
Overall, the manuscript is rather confusing.
The SSR theorem is stated (with no real intuition and the actual bounds on n(s) left for the reader to derive). It is not well motivated. Why would we want expected counts and not the discounted version?
Then the remainder of the paper actually makes no use of this theorem, but only use it as a distant inspiration. Tentative connections are made such as TD underestimating SR thus leading to a result more akin to SSR, which is highly speculative. It is also irrelevant since features are learned anyway.
The final proposed architecture has many additions to a simple DQN (the reconstruction + the exploration bonus + the MMC). This makes it difficult to understand what the contribution of the exploration bonus is.
It does not help that results are manually extracted from histograms found in  papers.
Overall, although the intuition is interesting (though not so new).
The overall motivation and structure of this manuscript makes think it does not match the standards of ICLR for publication