# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 3 Long-Term Visitation Value for Deep Exploration
### W-Function Initialization and Bounds  
In UCB bandits, it is assumed that each arm/action will be executed once before actions are executed twice. In order to enforce this, we need to make sure that the upper confidence bound \(U_{W}(s,a)\) is high enough so that an action cannot be executed twice before all other actions are executed once. Below, we discuss how to initialize the W-functions and set bounds in order to achieve the same behavior. For the sake of simplicity, below we drop subscripts and superscripts, i.e., we write \(Q(s,a)\) in place of \(Q^{\pi}(s,a)\), and \(W(s,a)\) in place of \(W^{\beta}_{\text{ics}}(s,a)\) or \(W^{\beta}_{\text{ics}}(s,a)\). \(W^{\beta}_{\text{ics}}\)**upper bound. ** To compute the initialization value we consider the worst-case scenario, that is, in state \(s\) all actions \(a\) but \(\bar{a}\) have been executed. In this scenario, we want that \(W(s,\bar{a})\) is an upper bound of \(W(s,a)\). Following Equations (12) and (14), we have  
\[Q_{\text{max}}+\kappa(1-\gamma_{w})W(s,\bar{a})=Q_{\text{max}}+\kappa(1-\gamma _{w})\bigg{(}\sqrt{2\text{log}(|\mathcal{A}|-1)}+\gamma_{w}\text{max}_{a}W(s^ {\prime},a)\bigg{)}, \tag{20}\]  
where the blue term is the TD target for non-terminal states, and \(\sqrt{2\text{log}(|\mathcal{A}|-1)}\) is the immediate visitation reward for executing \(\bar{a}\) in the worst-case scenario (all other \(|\mathcal{A}|-1\) actions have been executed, and \(\bar{a}\) has not been executed yet). In this scenario, \(W(s,\bar{a})\) is an upper bound of \(W(s,a)\) under the assumption of uniform count, i.e.,  
\[\forall(s,a)\
eq(s,\bar{a}),\ \ \ n(s,a)=\bar{n}(s)\Rightarrow W(s,\bar{a}) \geq W(s,a). \tag{21}\]  
We can then write Equation (20) as  
\[Q_{\text{max}}+\kappa(1-\gamma_{w})W(s,\bar{a})=Q_{\text{max}}+\kappa(1- \gamma_{w})(\sqrt{2\text{log}(|\mathcal{A}|-1)}+\gamma_{w}W(s,\bar{a})). \tag{22}\]  
In order to guarantee to select \(\bar{a}\), which has not been select yet, we need to initialize \(W(s,\bar{a})\) such that the following is satisfied  
\[Q_{\text{min}}+\kappa(1-\gamma_{w})W(s,\bar{a})>Q_{\text{max}}+\kappa(1- \gamma_{w})(\sqrt{2\text{log}(|\mathcal{A}|-1)}+\gamma_{w}W(s,\bar{a})), \tag{23}\]  
where \(Q_{\text{min}}\) denotes the smallest possible Q-value. We get  
\[W(s,\bar{a})>\frac{Q_{\text{max}}-Q_{\text{min}}}{\kappa(1-\gamma _{w})}+\sqrt{2\log(|\mathcal{A}|-1)}+\gamma_{w}W(s,\bar{a})\] \[W(s,\bar{a})>\frac{Q_{\text{max}}-Q_{\text{min}}}{\kappa(1- \gamma_{w})^{2}}+\frac{\sqrt{2\log(|\mathcal{A}|-1)}}{(1-\gamma_{w})}. \tag{24}\]  
Initializing the W-function according to Equation (24) guarantees to select \(\bar{a}\). Figure 4: **Toy example (part 2). ** Visitation count (**a**) and behavior policies derived from the proposed W-functions (**b**,**c**). Due to the low count, the exploration upper bound dominates the greedy Q-value, and the proposed behavior policies successfully achieve long-term exploration. Both policies prioritize unexecuted actions and avoid terminal and prison states. \(W_{\mathbf{s}}^{\beta}\) **upper bound. ** Since this W-function represents the discounted cumulative count, it is initialized to zero. However, numerical problems may occur in the square root of Equation (19) because the pseudocount can be smaller than one or even zero. In these cases, the square root of negative numbers and the division by zero are not defined. To address these issues, we add +1 inside the logarithm and replace the square root with an upper bound when \(\hat{n}(s,a)=0\). Similarly to the previous section, the bound needs to be high enough so that an action cannot be executed twice before all other actions are executed once.