# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 4 Evaluation
### Part 1: Discounted Return and States Discovered
#### 4.1.1 Deep Sea  
In this environment (Figure 7), the agent (the ship) always starts at the top-left corner of a gridworld of size \(N\times N\), and has to descend through the grid to a chest in the bottom-right corner. At the beginning of the episode, either a treasure or a bomb appear inside the chest, with a 50-50 chance. The outcome is known to the agent, as the state consists of the ship position and a flag denoting if the bomb or the treasure has appeared. At every step, the ship descends by one step and must choose to turn left or right. If it hits the left boundary, it will descend without turning. For example, from the starting position \((1,1)\), doing \"left\" will move the ship to \((2,1)\), while doing \"right\" will move it to \((2,2)\). The episode ends when the ship reaches the bottom of the grid, and thus the horizon is fixed to \(N\). The reward is \(1\) if the ship finds the treasure, \(-1\) if it finds the bomb, and \(-0.01/N\) if the ship goes \"right\" in any cell along the diagonal (denoted by sea waves). The optimal policy selects always \"right\" if there is the treasure, otherwise \"left\" at the initial state and then can act randomly.  
The challenge of this environment lies in having to select the same action (\"right\") \(N\) times in a row in order to receive either \(1\) or \(-1\). Doing \"left\" even only once prevents the ship from reaching the chest. At the same time, the agent is discouraged from doing \"right\", since doing so along the diagonal yields an immediate penalty. Consequently, an \(\epsilon\)-greedy policy without optimistic initialization would perform poorly, as the only short-term reward it receives would discourage it from doing \"right\". A random policy is also highly unlikely to reach the chest. In particular, the probability such a policy reaches it in any given episode is \((1/2)^{N}\). Thus, the expected number of episodes before observing either the bomb or the treasure is \(2^{N}\). Even for a moderate value of \(N=50\), this is an impractical number of episodes [4].  
Figure 7: The deep sea.  
**Results.** Figure 8 shows the results on a grid of depth \(N=50\). Since this domain has a fixed horizon, the evaluation does not include the \"short vs. long horizon\" comparison. With zero initialization, only our algorithms and bootstrapping by [PERSON] et al. [9] and [PERSON] et al. [4] discover all states and converge to the optimal policy within steps limit. Both proposed visitation-count-based (blue and orange) outperform the other two, converging twice or more as faster. Bootstrapped exploration with random prior (green) comes second, reproducing the results reported by [PERSON] et al. [52] and [PERSON] et al. [4]. Results with optimistic initialization are similar, with the main difference being that also approximate Thompson sampling by [PERSON] et al. [46] (purple) converges. Bootstrapping by [PERSON] et al. [52] (green) matches the performance of visitation-count-based with UCB (blue), and the two lines almost overlap. For more details about the percentage of successful trials and the percentage of states discovered by each algorithm with confidence intervals, we refer to Table 1.  
This evaluation shows that the proposed exploration outperforms state-of-the-art bootstrapping on a domain with a fixed horizon and no local optima. In the next sections, we investigate domains with absorbing states, i.e., that can prematurely end the episode, and distractor reward. In Section 4.2.3, we also present an empirical study on sample complexity on varying the deep sea depth \(N\). Furthermore, in Section 4.2.1, we show the state visitation count at the end of the learning for the deep sea and other domains, discussing why the proposed visitation-value-based exploration achieves new state-of-the-art results.