of times. However, the convergence of Watkins’ Q-learning can be prohibitively slow in MDPs where $\epsilon$-greedy action selection explores state space randomly. Later work developed reinforcement learning algorithms with provably fast (polynomial-time) convergence (@kearns2002near [@brafman2002r; @strehl2006pac]). At the core of these provably-optimal learning methods is some exploration strategy, which actively encourages the agent to visit novel state-action pairs. For example, R-MAX optimistically assumes that infrequently-visited states provide maximal reward, and delayed $Q$-learning initializes the $Q$-function with high values to ensure that each state-action is chosen enough times to drive the value down.

Since the theoretically sound RL algorithms are not computationally practical in the deep RL setting, deep RL implementations often use simple exploration methods such as $\epsilon$-greedy and Boltzmann exploration, which are often sample-inefficient and fail to find good policies. One common approach of exploration in deep RL is to construct an exploration bonus, which adds a reward for visiting state-action pairs that are deemed to be novel or informative. In particular, several prior methods define an exploration bonus based on a density model or dynamics model. Examples include VIME by @houthooft2016vime, which uses variational inference on the forward-dynamics model, and @tang2016exploration, @bellemare2016unifying, @ostrovski2017count, @fu2017ex2. While these methods yield 