# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## Appendix A Experiment Details
### Infinite Memory vs. No Memory  
Except for the chainworld in Section 4.2.4, the evaluation in Section 4 was conducted with Q-learning with infinite replay memory, following the same setup of [PERSON] et al. [4] as described in Section A.1. Here, we present additional results without replay memory, i.e., using classic Q-learning by [PERSON] [22] which updates the Q-tables using only the current transition. We show that the proposed method benefits the most from the replay memory, but can learn even without it while other algorithms cannot. We compare \(e\)-greedy exploration, our proposed visitation-value-based exploration, and bootstrapped exploration. Nevertheless, the latter needs a replay memory to randomize the Q-tables update, as each Q-table is updated using different random samples. Thus, for bootstrapped Q-learning, we compare the use of finite memory and small batches to infinite memory and large batches. Algorithm 1 describes the generic scheme of Q-learning without replay memory. The only difference from Algorithm 1 is the absence of the loop over the memory. The same modification is done to Algorithms 1 and 2 to derive the version of our algorithms without infinite memory. Bootstrapped Q-learning is the same as Algorithm 2 but with finite memory. The finite memory keeps at most \(20H\) steps, where \(H\) is the episode horizon, and uses mini-batches of 32 samples instead of 1024. ```
1 Initialize \(Q_{0}^{\beta}(s,a)\), \(Q_{0}^{\pi}(s,a)\), \(i=0\)
2 While \(i<i_{\text{reward}}\) do
3 Reset environment to state \(s_{1}\)
4 For \(t=1...H\) or until \(s_{t}\) is terminal
5 Select action according to \(a_{t}\sim\beta(\cdot|s_{t})\)
6 Transition to \(s_{t+1}=\mathcal{P}(s_{t+1}|s_{t},a_{t})\) and receive reward \(r_{t}=\mathcal{R}(s_{t},a_{t})\)
7 Store tuple \((s_{t},a_{t},r_{t},s_{t+1})\)
8\(\delta(s_{t},a_{t},s_{t+1})= \begin{cases}r_{t}-Q_{i}(s_{t},a_{t})&\text{if $s_{t}$ is terminal}\\ r_{t}+\gamma\max_{a}Q_{i}(s_{t+1},a)-Q_{i}(s_{t},a_{t})&\text{otherwise}\end{cases} \)
9\(Q_{i+1}(s_{t},a_{t})\gets Q_{i}(s_{t},a_{t})+\eta\delta(s_{t},a_{t},s_{t+ 1})\)
10 Update budget counter: \(i\gets i+1\)
```  
**Algorithm 1**Classic Tabular Q-Learning \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & **Deep Sea** & **Taxi** & **Deep Grid.** & **Grid. (Toy)** & **Grid. (Prison)** & **Grid. (Wall)** \\ \hline Optimal & Depth & 29 & 11 & 9 & 9 & 135 \\ \hline Short H. & Depth & 33 & 55 & 11 & 11 & 330 \\ \hline Long H. & Depth & 66 & 110 & 22 & 22 & 660 \\ \hline Stochastic & - & - & 55 & 15 & 25 & - \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Time horizons \(H\) for the tabular MDPs presented in Section 4. ```
1 Initialize \(Q_{0}^{b}(s,a)\) for \(b=1\ldots B\), \(Q_{0}^{\pi}(s,a)=0,i=0\)
2 While \(i<i_{\textsc{ideal}}\) do
3 Reset environment to state \(s_{1}\)
4 Select random Q-table: \(Q_{i}^{\beta}(s,a)\sim\text{unif}\{Q_{i}^{1}(s,a),\ldots,Q_{i}^{B}(s,a)\}\)
5 For \(t=1...H\) or until \(s_{t}\) is terminal
6 Select action according to the \(e\)-greedy policy of \(Q_{i}^{\beta}(s,a)\)
7 Transition to \(s_{t+1}=\mathcal{P}(s_{t+1}|s_{t},a_{t})\) and receive reward \(r_{t}=\mathcal{R}(s_{t},a_{t})\)
8 Store tuple \((s_{t},a_{t},r_{t},s_{t+1})\)
9 For all tuples \((s,a,s^{\prime},r)\) in the replay memory
10 \(\delta^{\pi}(s,a,s^{\prime})= \begin{cases}r_{t}-Q_{i}^{\pi}(s,a)&\text{if $s$ is terminal}\\ r_{t}+\gamma\max_{a}Q_{i}^{\pi}(s^{\prime},a)-Q_{i}^{\pi}(s,a)&\text{otherwise} \end{cases} \)
11\(Q_{i+1}^{\pi}(s,a)\leftarrow Q_{i}^{\pi}(s,a)+\eta\delta^{\pi}(s,a,s^{\prime})\)
12 For all behavior Q-tables \(Q_{i}^{b}(s,a)\)
13 Sample mini-batch from the replay memory
14 For all tuples \((s,a,s^{\prime},r)\) in the mini-batch
15 \(\delta^{b}(s,a,s^{\prime})= \begin{cases}r_{t}-Q_{i}^{b}(s,a)&\text{if $s$ is terminal}\\ r_{t}+\gamma\max_{a}Q_{i}^{b}(s^{\prime},a)-Q_{i}^{b}(s,a)&\text{otherwise} \end{cases}