# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 3 Long-Term Visitation Value for Deep Exploration
### The Long-Term Visitation Value Approach
 \tag{17}\]  
Once again we distinguish between terminal and non-terminal states, but in the TD error the max operator has been replaced by the min operator. Contrary to the previous case, in fact, the lower the W-function the better, as we want to incentivize the visit of lower-count states. If we would use only the immediate count as reward for terminal states, the agent would be constantly driven there. Therefore, similarly to the UCB-based reward, we assume that the agent stays in terminal states forever getting the same reward. In the TD target, since we want to prioritize low-count state-action pairs, the min operator yields an optimistic estimate of the W-function, because the lower the W-function the more optimistic the exploration is. Assuming identical visitation over state-action pairs, the W-function becomes the discounted cumulative count, i.e.,  
\[W_{s}^{\beta}(s_{t},a_{t})=\frac{1}{1-\gamma_{w}}n(s_{t},a_{t}). \tag{18}\]  
We then compute the pseudocount \(\hat{n}(s_{t},a_{t})=(1-\gamma_{w})W_{s}^{\beta}(s_{t},a_{t})\) and use it in the UCB policy  
\[\beta(a_{t}|s_{t})=\arg\max_{a}\Big{\{}Q^{\pi}(s_{t},a)+\kappa\underbrace{ \sqrt{\frac{2\log\sum_{a_{t}}\hat{n}(s_{t},a_{j})}{\hat{n}(s_{t},a)}}}_{u_{W}^ {\beta}(s,a)}\Big{\}}. \tag{19}\]  
When the counts are zero, \(W_{s}^{\beta}(s,a)=0\), thus we need to initialize it to zero. We discuss how to avoid numerical problem in the square root in Section 3.3. Finally notice that when \(\gamma_{w}=0\), Equation (19) is equivalent to the UCB1 policy in Equation (5). **Example of Long-Term Exploration with the W-function. ** Consider again the toy problem presented in Section 3.1. Figure 4 shows the behavior policies of Equation (14) and Equation (19) with \(\gamma_{w}=0.99\). The policies are identical and both drive the agent to unvisited states, or to states where it has not executed all actions yet, successfully exhibiting long-term exploration. The only difference is the magnitude of the state-action pair values (the colormap, especially in unvisited states) due to their different initialization. 1. In (1,3), both select \"down\" despite \"up\" and \"left\" having lower count. The agent, in fact, knows that from (1,2) it can go \"down\" to (1,1) where it executed only one action. Thus, it knows that there it can try new actions. On the other hand, the only thing it knows about (2,3) is that it leads to the prison state, where the agent already executed all actions. Thus, (1,2) has a higher long-term exploration value than (2,3). 2. In (1,2) both select \"up\", overturning the greedy action \"down\" (Figure 3b). This is crucial because to fully explore the environment we need to select new actions. 3. The same happens in (2,3), where actions with count zero are selected, rather than the greedy ones. 4. None of the policies lead the agent to the prison state, because it has already been visited and all actions have been executed in there. 5. They both do not select \"right\" in (2,2) because it has been executed one more time than other actions. Nonetheless, the difference in the action value is minimal, as shown by the action colormap (almost uniform).