We present a new approach for efficient exploration which leverages a\nlow-dimensional encoding of the environment learned with a combination of\nmodel-based and model-free objectives. Our approach uses intrinsic rewards that\nare based on the distance of nearest neighbors in the low dimensional\nrepresentational space to gauge novelty. We then leverage these intrinsic\nrewards for sample-efficient exploration with planning routines in\nrepresentational space for hard exploration tasks with sparse rewards. One key\nelement of our approach is the use of information theoretic principles to shape\nour representations in a way so that our novelty reward goes beyond pixel\nsimilarity. We test our approach on a number of maze tasks, as well as a\ncontrol problem and show that our exploration approach is more sample-efficient\ncompared to strong baselines.\n