# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## Appendix A Experiment Details
### Infinite Memory vs. No Memory
\)
16 \(Q_{i+1}^{b}(s,a)\leftarrow Q_{i}^{b}(s,a)+\eta\delta^{b}(s,a,s^{\prime})\)
17 Update budget counter: \(i\gets i+1\)
```  
**Algorithm A6**Tabular Bootstrapped Q-Learning with Replay Memory  
**Results. ** Figure A1 shows the results on two gridworlds. The \"toy\" one has a single reward, while the \"prison\" one has also distractors. We refer to Section 4.1 for their full description. In the first domain, all algorithms perform well except for \(e\)-greedy exploration (green), which missed the reward in some trials. The use of infinite memory helped all algorithms, allowing bootstrap and visitation-value-based to learn substantially faster. For example, on average, without replay memory our algorithms (blue and orange) converged in 1000 steps, while with replay memory they took only 250 steps, i.e., \(\times 4\) times faster. Bootstrapped Q-learning (red), performance does not change substantially with finite and infinite memory. However, in the second domain only visitation-value-based exploration always learns, regardless of the memory. As discussed in Section 4.1, bootstrap performs poorly due to distractor rewards, and the infinite memory does not help it. For visitation-value-based exploration, the speed-up gained from the infinite memory is even larger than before, due to the higher complexity of the domain. In this case in fact, with infinite memory, it learns \(\times 4\) and \(\times 8\) times faster than without memory (blue and orange, respectively). This evaluation shows that the proposed method benefits the most from the replay memory, but can learn even without it while other algorithms cannot. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Algorithm** & **Discovery (\%)** & **Success (\%)** \\ \hline \multirow{8}{*}{Zero Init. \& Short Hor.} & **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) & \(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\) \\  & \(\epsilon\)-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}{*}{Opt. Init. \& Short Hor.} & **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) & \(100\pm 0\) & \(100\pm 0\) \\  & Bootstrap. (Osband 2016a) & \(100\pm 0\) & \(100\pm 0\) \\  & Bootstrap. ([PERSON] 2019) & \(99.94\pm 0.08\) & \(100\pm 0\) \\  & Expl. Bonus ([PERSON] 2008) & \(100\pm 0\) & \(100\pm 0\) \\  & \(\epsilon\)-greedy & \(100\pm 0\) & \(100\pm 0\) \\  & Random & \(29.56\pm 0.98\) & \(1.92\pm 1.49\) \\ \hline \multirow{8}{*}{Zero Init. \& Long Hor.} & **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) & \(76.38\pm 2.31\) & \(15.69\pm 2.93\) \\  & Bootstrap. ([PERSON] 2016a) & \(53.80\pm 6.63\) & \(29.85\pm 12.72\) \\  & Bootstrap. ([PERSON] 2019) & \(36.34\pm 3.16\) & \(6.54\pm 2.62\) \\  & UCB1 ([PERSON] 2002) & \(49.66\pm 2.45\) & \(8.35\pm 1.32\) \\  & Expl. Bonus ([PERSON] 2008) & \(92.83\pm 2.26\) & \(76.18\pm 16.09\) \\  & \(\epsilon\)-greedy & \(42.26\pm 2.52\) & \(7.66\pm 0.03\) \\  & Random & \(55.89\pm 0.98\) & \(2.06\pm 1.49\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Deep gridworld results recap.