# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## Appendix A Experiment Details
### The Generic Q-Learning Scheme  
In all experiments, we used Q-learning with infinite replay memory. Classic Q-learning by [PERSON] and [PERSON] [22] updates the Q-tables using only the current transition. The so-called _experience replay_, instead, keeps past transitions and uses them multiple times for successive updates. This procedure became popular with deep Q-learning [1] and brought substantial improvement to many RL algorithms. In our experiments, we followed the setup proposed by [PERSON] et al. [4] and used an infinite memory, i.e., we stored all transitions, since it allowed much faster learning than classic Q-learning. This can also be seen as Dyna-Q [60] without random memory sampling. In our experiments, the size of the domains does not pose any storage issue. When storage size is an issue, it is possible to fix the memory size and sample random mini-batches as in DQN [1]. More details in Appendix A.6. Algorithm A1 describes the generic scheme of Q-learning with infinite replay memory. TD learning is used on both \(Q^{\pi}(s,a)\) and \(Q^{\beta}(s,a)\), with the only difference being the initialization (\(Q^{\pi}(s,a)\) is always initialized to zero).  
Depending on \(\beta(a|s)\), we have different exploration strategies, i.e.,  
\[\beta(a_{t}|s_{t}) \sim\text{unif}\{\mathcal{A}\},\] random (A1) \[\beta(a_{t}|s_{t})\begin{cases}=\arg\max_{a}\left\{Q^{\beta}(s_{t },a)\right\}&\text{with probability $1-\epsilon$},\\ \sim\text{unif}\{\mathcal{A}\}&\text{with probability $\epsilon$},\end{cases} \epsilon\text{-greedy}\] (A2) \[\beta(a_{t}|s_{t}) =\arg\max_{a}\left\{Q^{\beta}(s_{t},a)+\kappa\sqrt{\frac{2\log \sum_{a_{j}}n(s_{t},a_{j})}{n(s_{t},a)}}\right\}.\] (A3)  
**Numerical stability and worst-case scenario.** For UCB1 [28], a visitation count \(n(s,a)\) is increased after every transition (see Algorithm A2, line 7). In classic bandit problems, UCB1 is initialized by executing all actions once, i.e., with \(n(s,a)=1\). In MDPs we cannot do that, i.e., we cannot arbitrarily set the agent in any state and execute all actions, thus \(n(s,a)=0\). Following the W-function bound in Section 3.3, we always add +1 inside the logarithm, and bound the square root to \((Q_{\max}-Q_{\min})/\kappa+\sqrt{2\log|\mathcal{A}|}\) when \(n(s,a)=0\). This correspond to the case where all actions but \(\tilde{a}\) has been executed once, and enforces the policy to choose \(\tilde{a}\). In our experiments, we set \(Q_{\max}=r_{\max}/(1-\gamma)\) and \(Q_{\min}=0\).  
```
1 Initialize \(Q_{0}^{\beta}(s,a)\), \(Q_{\pi}^{\alpha}(s,a),i=0\)
2 While \(i<i_{\text{inner}}\) 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 For all tuples \((s,a,s^{\prime},r)\) in the replay memory
9\(\delta(s,a,s^{\prime})=\begin{cases}r_{t}-Q_{i}(s,a)&\text{if $s$ is terminal}\\ r_{t}+\gamma\max_{a}Q_{i}(s^{\prime},a)-Q_{i}(s,a)&\text{otherwise}\\ Q_{i+1}(s,a)\gets Q_{i}(s,a)+\eta\delta(s,a,s^{\prime})\end{cases}\)
10 Update budget counter: \(i\gets i+1\)
```  
**Algorithm A1**Tabular Q-Learning with Replay Memory