# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 1 Introduction  
Reinforcement learning (RL) trains agents to behave in an environment by trial and error. The agent performs actions and, in turn, the environment may provide a _reward_, i.e., feedback assessing the quality of the action. The goal of RL is then to learn a _policy_, i.e., a function producing a sequence of actions yielding the highest cumulative reward. Despite its simplicity, RL achieved impressive results, such as beating Atari videogames from pixels [1, 2], or world-class champions at Chess, Go and Shogi [3]. However, a high-quality reward signal is typically necessary to learn the optimal policy, and without it, RL algorithms may perform poorly even in small environments [4]. **Characteristics of high-quality rewards. ** One important factor that defines the quality of the reward signal is the _frequency_ at which rewards are emitted. Frequently emitted rewards are called \"dense\", in contrast to infrequent emissions which are called \"sparse\". Since improving the policy relies on getting feedback via rewards, the policy cannot be improved until a reward is obtained. In situations where this occurs very rarely, the agent learns slowly or cannot learn at all. Furthermore, reinforcement signals should encourage the agent to find the best actions to solve the given task. However, the environment may also provide _distracting_ rewards, i.e., rewards that create suboptimal modes of the objective function. In this case, the agent should be able to extensively explore the environment without prematurely converging to locally optimal solutions caused by distracting rewards. **Reward engineering. ** In the presence of sparse distracting rewards, efficiently exploring the environment to learn the optimal policy is challenging. Therefore, many RL algorithms rely on well-shaped reward functions such as quadratic costs. For example, in a collect-and-deliver task, we could design an additional reward function that rewards proximity to the items to be collected. These well-shaped functions help to guide the agent towards good solutions and avoid bad local optima. However, from the perspective of autonomous learning, this so-called reward engineering is unacceptable for three reasons. First, the commonly utilized reward functions heavily restrict the solution space and may prevent the agent from learning optimal behavior (especially if no solution to the task is known). Second, it is easy to misspecify the reward function and cause unexpected behavior. For instance, by getting excessively high rewards for proximity to the items the agent may never learn to deliver them. Third, reward engineering requires manual tuning of the reward function and the manual addition of constraints. This process requires expertise and the resulting reward function and constraints may not transfer to different tasks or environments. _In this paper, we address the problem of reinforcement learning with sparse rewards without relying on reward engineering or requiring prior knowledge about the environment or the task to solve. In particular, we highlight the problem of learning in the presence of rewards that create suboptimal modes of the objective function, which we call \"distractors\"._  
**The exploration-exploitation dilemma. ** Learning when rewards are sparse and possibly distracting challenges classic RL algorithms. Initially, the agent has no prior knowledge about the environment and needs to explore it searching for feedback. As it gathers rewards, the agent develops a better understanding of the environment and can estimate which actions are \"good\", i.e., yield positive rewards, and which are not. Then, at any point, it needs to decide whether it should explore the environment searching for better rewards by executing new actions, or exploit its knowledge and execute known good actions. This \"exploration-exploitation dilemma\" is frequently addressed naively by dithering [1, 5].