  Reinforcement learning with sparse rewards is still an open challenge.
Classic methods rely on getting feedback via extrinsic rewards to train the
agent, and in situations where this occurs very rarely the agent learns slowly
or cannot learn at all. Similarly, if the agent receives also rewards that
create suboptimal modes of the objective function, it will likely prematurely
stop exploring. More recent methods add auxiliary intrinsic rewards to
encourage exploration. However, auxiliary rewards lead to a non-stationary
target for the Q-function. In this paper, we present a novel approach that (1)
plans exploration actions far into the future by using a long-term visitation
count, and (2) decouples exploration and exploitation by learning a separate
function assessing the exploration value of the actions. Contrary to existing
methods which use models of reward and dynamics, our approach is off-policy and
model-free. We further propose new tabular environments for benchmarking
exploration in reinforcement learning. Empirical results on classic and novel
benchmarks show that the proposed approach outperforms existing methods in
environments with sparse rewards, especially in the presence of rewards that
create suboptimal modes of the objective function. Results also suggest that
our approach scales gracefully with the size of the environment. Source code is
available at https://github.com/sparisi/visit-value-explore
