# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 1 Introduction
In continuous action spaces Gaussian noise is added to the action, while in discrete spaces actions are chosen \(\epsilon\)-greedily, i.e., optimally with probability \(1-\epsilon\) and randomly with probability \(\epsilon\). Typically, the initial noise and \(\epsilon\) are large and then decay over time. These approaches work in environments where random sequences of actions are likely to cause positive rewards. However, if rewards are sparse or are given only for specific sequences of actions, it is very unlikely that the agent will receive any feedback. In this case, the worst-case sample complexity for learning the optimal policy with dithering exploration is exponential in the number of states and actions [6, 7, 8]. Furthermore, if distractor rewards are easily reachable, the agent may prematurely converge to local optima. An example of this problem is depicted in Figure 1.  
**Deep exploration. ** Well-performing exploration strategies should solve long-horizon problems with sparse and possibly distracting rewards in large state-action spaces while remaining computationally tractable. This can be achieved if the agent takes several coherent actions to explore unknown states instead of just locally choosing the most promising  
Figure 1: A simple problem where naive exploration performs poorly. The agent starts in the second leftmost cell and is rewarded only for finding a treasure. It can move up/down/left/right, but if it moves up or down its position resets. Acting randomly at each step takes on average \(4^{N}\) attempts to find the rightmost and most valuable reward, where \(N\) is the number of cells to the right of the agent. As no reward is given in any intermediate cell, \(\epsilon\)-greedy exploration is likely to converge to the local optimum represented by the leftmost reward if \(\epsilon\) decays too quickly. actions. These behaviors are usually referred to as \"deep exploration\" and \"myopic exploration\", respectively, [9]. RL literature has a long history of algorithms for deep exploration, even though the term \"deep\" became popular only in recent years. The first algorithms to guarantee full exploration of tabular environments date back to [PERSON] [10] and [PERSON] [11]. These algorithms learn a model of the environment, i.e., the transition and reward functions, and plan actions accordingly to a state-action visitation count to favor less-visited states. Since then, other model-based [12; 13] as well as model-free algorithms [14; 15; 16; 17] have been proposed. However, despite their strong guarantees, these algorithms either require learning the complete model of the environment, rely on optimistic initialization, or have impractically high sample complexity. In continuous environments, intrinsic motivation and bootstrapping are the most prominent approaches. The former defines an additional _intrinsic_ reward added to the environment _extrinsic_ reward. If the extrinsic reward is sparse, the intrinsic reward can fill the gaps between the sparse signals, possibly giving the agent quality feedback at every timestep. This approach can be used in conjunction with any RL algorithm by just providing the modified reward signal. However, the quality of exploration strongly depends on the intrinsic reward, which may not scale gracefully with the extrinsic reward and therefore needs hand-tuning. Furthermore, combining exploration and exploitation by summing intrinsic and extrinsic rewards can result in undesired behavior due to the non-stationarity of the augmented reward function. Moreover, convergence is harder to guarantee [18], and in general, there is no agreement on the definition of the best intrinsic reward [19; 20]. Bootstrapping, instead, is used to estimate the actions value posterior distribution over the environment, which then drives exploration. Because actions are selected considering the level of uncertainty associated with their value estimates, bootstrapping incentivizes experimentation with actions of highly uncertain value and, thus, induces exploration [4].