Unifying Count-Based Exploration and Intrinsic Motivation
We consider an agent's uncertainty about its environment and the problem of generalizing this uncertainty across states. Specifically, we focus on the problem of exploration in non-tabular reinforcement learning. Drawing inspiration from the intrinsic motivation literature, we use density models to measure uncertainty, and propose a novel algorithm for deriving a pseudo-count from an arbitrary density model. This technique enables us to generalize count-based exploration algorithms to the non-tabular case. We apply our ideas to Atari 2600 games, providing sensible pseudo-counts from raw pixels. We transform these pseudo-counts into exploration bonuses and obtain significantly improved exploration in a number of hard games, including the infamously difficult MONTEZUMA'S REVENGE.
This paper has multiple contributions: 1. an extension to counting-based exploration based on sequential density model; 2. a simple but effective modification to DQN; 3. impressive empirical results incl. progress towards solving Montezuma's Revenge; 4. a connection to intrinsic motivation (more comments on this topic in detailed review below)
Overall this paper is a good paper that should be accepted. In particular, the formulation of pseudo-count seems novel, and Montezuma's Revenge experiment demonstrated convincingly the method can be effectively applied.  I have however 2 concerns that I'd like the authors to address/respond to:  1. As stressed in title and in line 206, the claimed main result is the relationship between pseudo-count and information gain (IG), which is a classic concept in intrinsic motivation literature. The stated relationship, though technically sound, doesn't seem to relate to existing intrinsic motivation literature. I'd be happy to be corrected but as far as I can tell, the term "Information gain" here is used to define a quantity that's both technically and philosophically different from the usual Information gain.  Specifically IG in this paper is defined over information gain over a mixture sequential density models of state visitations whereas IG is usually defined as information gain of "model of the environment" [1,2]. Philosophically, IG is introduced to create a "knowledge-seeking agent ... to gain as much information about its environment as possible" [2] and this is a characteristic that the "IG" definition in this paper fundamentally lacks. The reason is that if the behavior policy changes, there will always be information gain of state density model because state visitation frequencies change as the policy changes yet this specific "IG" doesn't need to reveal anything new about the environment, hence making the "IG" used in this paper distinctly different from the classic notion.  The connection between "IG", PG, and pseudo-count is an interesting one but I'm wondering if the authors can justify how it "connects to intrinsic motivation", and "unifies count-based exploration and intrinsic motivation"?  2. Can the authors discuss more why pseudo-count is preferable to PG? From figure 2 in appendix it seems PG performs very competitively without extra tweaking on selecting what function to use to transform it but the inverse pseudo-count performs poorly with the /sqrt transformation. I suspect that if similar PG can be tried with different transformations it's going to outperform the tweaked pseudo-count bonus. Proof of Theorem 2 also indicates that 1/pseudo-count >= e^PG - 1. Since 1/psudo-count is exponentially larger than PG, it'd not be surprising that PG is better-behaved than 1/pseudo-count. I'm wondering if the authors can clarify if pseudo-count has distinctive advantages over PG or they are more of less interchangeable?   [1]: Sun, Yi, Faustino Gomez, and Jürgen Schmidhuber. "Planning to be surprised: Optimal bayesian exploration in dynamic environments." International Conference on Artificial General Intelligence. Springer Berlin Heidelberg, 2011. [2]: Orseau, Laurent, Tor Lattimore, and Marcus Hutter. "Universal knowledge-seeking agents for stochastic environments." International Conference on Algorithmic Learning Theory. Springer Berlin Heidelberg, 2013.