Exploration is critical for deep reinforcement learning in complexenvironments with high-dimensional observations and sparse rewards. To addressthis problem, recent approaches proposed to leverage intrinsic rewards toimprove exploration, such as novelty-based exploration and prediction-basedexploration. However, many intrinsic reward modules require sophisticatedstructures and representation learning, resulting in prohibitive computationalcomplexity and unstable performance. In this paper, we propose RewardingEpisodic Visitation Discrepancy (REVD), a computation-efficient and quantifiedexploration method. More specifically, REVD provides intrinsic rewards byevaluating the R\'enyi divergence-based visitation discrepancy betweenepisodes. To make efficient divergence estimation, a k-nearest neighborestimator is utilized with a randomly-initialized state encoder. Finally, theREVD is tested on Atari games and PyBullet Robotics Environments. Extensiveexperiments demonstrate that REVD can significantly improves the sampleefficiency of reinforcement learning algorithms and outperforms thebenchmarking methods.