# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## Appendix A Experiment Details
### Q-Learning with Visitation Value  
Algorithms3 and A4 describe the novel method proposed in this paper. In our experiments \(\kappa=r_{\max}/(1-\gamma)\) and \(\gamma_{w}=0.99\). For the chainworld in Section 4.2.4 we set \(\gamma_{w}=0.999\). With infinite horizon, in fact, this yielded better results by allowing the agent to explore for longer. For the stochastic gridworld in Section 4.2.5 we set \(\gamma_{w}=0.9\). As discussed in the results, in fact, a stochastic transition function naturally improves exploration, thus a smaller visitation discount was sufficient and yielded better results. ```
1 Initialize \(Q_{0}^{\beta}(s,a)\), \(Q_{0}^{\pi}(s,a)=0,W_{\textsc{cc},0}^{\beta}(s,a),n(s,a)=0,i=0\)
2 While \(i<i_{\textsc{weak}}\) do
3 Reset environment to state \(s_{1}\)
4 For \(t=1...H\) or until \(s_{t}\) is terminal
5 Select action according to \(\beta(a_{t}|s_{t})=\arg\max_{a}\Bigl{\{}Q_{i}^{\beta}(s_{t},a)+\kappa(1-\gamma _{w})W_{\textsc{cc},i}^{\beta}(s_{t},a)\Bigr{\}}\)
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 Update visitation count: \(n(s_{t},a_{t})\gets n(s_{t},a_{t})+1\)
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(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}\end{cases} \)
11 \(Q_{i+1}(s,a)\gets Q_{i}(s,a)+\eta\delta(s,a,s^{\prime})\)
12 Compute visitation reward according to Equation (10)
13 \(\delta^{W}(s,a,s^{\prime})= \begin{cases}r_{t}^{W}-W_{\textsc{cc},i}^{\beta}(s,a )&\text{if $s$ is terminal}\\ r_{t}^{W}+\gamma\max_{a}W_{\textsc{cc},i}^{\beta}(s^{\prime},a)-W_{\textsc{ cc},i}^{\beta}(s,a)&\text{otherwise}\end{cases} \)
14 \(W_{\textsc{cc},i+1}^{\beta}(s,a)\gets W_{\textsc{cc},i}^{\beta}(s,a)+\eta \delta^{W}(s,a,s^{\prime})\)
15 Update budget counter: \(i\gets i+1\)
```  
**Algorithm A3**Tabular Q-Learning with Replay Memory and Visit. Value (UCB)  
### Q-Learning with Visitation Value  
Algorithms3 and A4 describe the novel method proposed in this paper. In our experiments \(\kappa=r_{\max}/(1-\gamma)\) and \(\gamma_{w}=0.999\). For the chainworld in Section 4.2.4 we set \(\gamma_{w}=0.999\). With infinite horizon, in fact, this yielded better results by allowing the agent to explore for longer. For the stochastic gridworld in Section 4.2.5 we set \(\gamma_{w}=0.9\). As discussed in the results, in fact, a stochastic transition function naturally improves exploration, thus a smaller visitation discount was sufficient and yielded better results. ```
1 Initialize \(Q_{0}^{\beta}(s,a)\), \(Q_{0}^{\pi}(s,a)=0,n(s,a)=0\), \(W_{s,0}^{\beta}(s,a)=0,i=0\)
2 While \(i<i_{\textsc{newdict}}\) do
3 Reset environment to state \(s_{1}\)
4 For \(t=1...H\) or until \(s_{t}\) is terminal
5 Compute pseudocount: \(\hat{n}(s_{t},a)=(1-\gamma_{w})W_{s,t}^{\beta}(s_{t},a)\)
6 Select action according to \[\beta(a_{t}|s_{t})=\arg\max_{a}\left\{Q_{i}^{\beta}(s_{t},a)+\kappa\sqrt{\frac{2 \log\sum_{s_{t}}\hat{n}(s_{t},a_{t})}{\hat{n}(s_{t},a)}}\right\}\] 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 Update visitation count: \(n(s_{t},a_{t})\gets n(s_{t},a_{t})+1\)
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(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}\end{cases} \)
11\(Q_{i+1}(s,a)\gets Q_{i}(s,a)+\eta\delta(s,a,s^{\prime})\)
12 Compute visitation reward according to Equation (15)
13\(\delta^{W}(s,a,s^{\prime})= \begin{cases}r_{t}^{W}-W_{s,t}^{\beta}(s,a)&\text{if $s$ is terminal}\\ r_{t}^{W}+\gamma\min_{a}W_{s,t}^{\beta}(s^{\prime},a)-W_{s,t}^{\beta}(s,a)& \text{otherwise}\end{cases}