# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 4 Evaluation
### Part 2: In-Depth Investigation  
In this section, we present an in-depth analysis of issues associated with learning with sparse rewards, explaining in more detail why our approach outperformed existing algorithms in the previous evaluation. We start by reporting the visitation count at the end of the learning, showing that our algorithms explore the environment uniformly. We continue with a study on the impact of the visitation discount \(\gamma_{w}\), showing how it affects the performance of the W-function. Next, we present the empirical sample complexity analysis of all algorithms on the deep sea domain, showing that our approach scales gracefully with the number of states. Finally, we evaluate the algorithms in the infinite horizon setting and stochastic MDPs, evaluating the accuracy of the Q-function and the empirical sample complexity. Even in these scenarios, our approach outperforms existing algorithms. Figure 17: **The “prison” and distractors affect the performance of all algorithms but ours. **  
Figure 18: **The final gridworld emphasizes the better performance of our algorithms. **  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Algorithm** & **Discovery (\%)** & **Success (\%)** \\ \hline \multirow{8}{*}{Deep Sea} & **Ours (UCB Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & **Ours (Count Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & Rand. Prior ([PERSON] 2019) & \(99.90\pm 0.01\) & \(100\pm 0\) \\  & Bootstrap. ([PERSON] 2016a) & \(99.77\pm 0.05\) & \(100\pm 0\) \\  & Bootstrap. ([PERSON] 2019) & \(63.25\pm 3.31\) & \(0\pm 0\) \\  & UCB1 ([PERSON] 2002) & \(55.72\pm 0.34\) & \(0\pm 0\) \\  & Expl. Bonus ([PERSON] 2008) & \(85.65\pm 1.0\) & \(0\pm 0\) \\  & \(e\)-greedy & \(57.74\pm 1.11\) & \(0\pm 0\) \\  & Random & \(58.59\pm 1.35\) & \(0\pm 0\) \\ \hline \multirow{8}{*}{Taxi} & **Ours (UCB Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & **Ours (Count Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & Rand. Prior (Osband 2019) & \(69.60\pm 2.96\) & \(13.07\pm 2.96\) \\  & Bootstrap. ([PERSON] 2016a) & \(52.44\pm 7.55\) & \(18.77\pm 9.24\) \\  & Bootstrap. ([PERSON] 2019) & \(22.44\pm 1.81\) & \(1.9\pm 1.47\) \\  & UCB1 ([PERSON] 2002) & \(31.17\pm 0.70\) & \(1.53\pm 1.37\) \\  & Expl. Bonus ([PERSON] 2008) & \(74.62\pm 2.24\) & \(17.6\pm 2.56\) \\  & \(e\)-greedy & \(29.64\pm 0.98\) & \(1.92\pm 1.49\) \\  & Random & \(29.56\pm 0.98\) & \(1.92\pm 1.49\) \\ \hline \multirow{8}{*}{Deep Gridworld} & **Ours (UCB Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & **Ours (Count Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & Rand. Prior ([PERSON] 2019) & \(99.8\pm 0.39\) & \(100\pm 0\) \\  & Bootstrap. ([PERSON] 2016a) & \(99.2\pm 0.72\) & \(100\pm 0\) \\  & Bootstrap. ([PERSON] 2019) & \(84.8\pm 4.33\) & \(40\pm 21.91\) \\  & UCB1 ([PERSON] 2002) & \(97.4\pm 0.99\) & \(50\pm 22.49\) \\  & Expl. Bonus ([PERSON] 2008) & \(99.8\pm 0.39\) & \(100\pm 0\) \\  & \(e\)-greedy & \(97.4\pm 1.17\) & \(45\pm 22.25\) \\  & Random & \(97.2\pm 1.15\) & \(45\pm 22.25\) \\ \hline \multirow{8}{*}{Gridworld (Toy)} & **Ours (UCB Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & **Ours (Count Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & Rand. Prior ([PERSON] 2019) & \(72.39\pm 6.9\) & \(44.44\pm 14.69\) \\  & Bootstrap. ([PERSON] 2016a) & \(64.35\pm 11.1\) & \(33.03\pm 8.54\) \\  & Bootstrap. ([PERSON] 2019) & \(54.78\pm 6.69\) & \(25.61\pm 8.39\) \\  & UCB1 ([PERSON] 2002) & \(80.78\pm 2.56\) & \(32.31\pm 4.11\) \\  & Expl. Bonus ([PERSON] 2008) & \(85.87\pm 3\) & \(46.96\pm 12.35\) \\  & \(e\)-greedy & \(58.38\pm 5.27\) & \(22.84\pm 2.48\) \\  & Random & \(76.96\pm 3.08\) & \(35.36\pm 10.37\) \\ \hline \multirow{8}{*}{Gridworld (Prison)} & **Ours (UCB Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & **Ours (Count Reward)** & \(\mathbf{100\pm 0}\) & \(\mathbf{100\pm 0}\) \\  & Rand. Prior ([PERSON] 2019) & \(72.39\pm 6.9\) & \(44.44\pm 14.69\) \\  & Bootstrap.