# 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
** The visitation reward is the UCB of the state-action count at the current time, i.e.,  
\[r_{t}^{W}= \begin{cases}\sqrt{\frac{2\log\sum_{a_{t}}n(s_{t},a_{j})}{n(s_{t},a _{t})}}&\text{if $s_{t}$ is non-terminal}\\ \frac{1}{1-\gamma_{w}}\sqrt{\frac{2\log\sum_{a_{t}}n(s_{t},a_{j})}{n(s_{t},a_ {t})}}&\text{otherwise.}\end{cases}  \tag{10}\]  
This W-function represents the discount-weighted average UCB along the trajectory, i.e.,  
\[W^{\beta}_{(cs}(s_{t},a_{t})=\sum_{i=t}^{H}\gamma_{w}^{i-t}\sqrt{\frac{2\log \sum_{a_{t}}n(s_{i},a_{j})}{n(s_{i},a_{i})}}, \tag{11}\]  
and its TD error is  
\[\delta^{W}(s_{t},a_{t},s_{t+1})= \begin{cases}r_{t}^{W}+\gamma_{w}\max_{a}W^{ \beta}_{(cs,i}(s_{t+1},a)-W^{\beta}_{(cs,i}(s_{t},a_{t})&\text{if $s_{t}$ is non-terminal}\\ r_{t}^{W}-W^{\beta}_{(cs,i}(s_{t},a_{t})&\text{otherwise.}\end{cases}  \tag{12}\]Notice how we distinguish between terminal and non-terminal states for the reward in Equation (10). The visitation value of terminal states, in fact, is equal to the visitation reward alone, as denoted by the TD target in Equation (10). Consequently, the visitation value of terminal states could be significantly smaller than the one of other states, and the agent would not visit them again after the first time. This, however, may be detrimental for learning the Q-function, especially if terminal states yield high rewards. For this reason, we assume that the agent stays in terminal states forever, getting the same visitation reward at each time step. The limit of the sum of the discounted reward is the reward in Equation (10). Furthermore, given proper initialization of \(W^{\beta}_{\text{cs}}\) and under some assumptions, the target of non-terminal states will still be higher than the one of terminal states despite the different visitation reward, if the count of the former is smaller. We will discuss this in more detail later in this section. Another key aspect of this W-function regards the well-known overestimation bias of TD learning. Since we can only update the W-function approximately based on limited samples, it is beneficial to overestimate its target with the max operator, while it is known that in highly stochastic environments the overestimation can degrade the performance of value-based algorithm [53; 54], it has been shown that underestimation does not perform well when the exploration is challenging [55], and for a wide class of environments, overestimation allows finding the optimal solution due to self-correction [56]. Assuming identical visitation over state-action pairs, the W-function becomes the discounted immediate UCB, i.e.,  
\[W^{\beta}_{\text{cs}}(s_{t},a_{t})=\frac{1}{1-\gamma_{w}}\sqrt{\frac{2\log \sum_{a_{t}}n(s_{t},a_{t})}{n(s_{t},a_{t})}}, \tag{13}\]  
thus, we can use \(W^{\beta}_{\text{cs}}(s,a)\) directly in the behavior policy  
\[\beta(a_{t}|s_{t})=\arg\max_{a}\Big{\{}Q^{\pi}(s_{t},a)+\kappa\underbrace{(1- \gamma_{w})W^{\beta}_{\text{cs}}(s_{t},a)}_{\text{U}^{\text{DD}}_{\text{ss}}( s,a)}\Big{\}}, \tag{14}\]  
In Section 3.3, we discuss how to initialize \(W^{\beta}_{\text{cs}}(s,a)\). Finally, notice that when \(\gamma_{w}=0\), Equation (13) is the classic UCB, and Equation (14) is equivalent to the UCB1 policy in Equation (5). **W-function as long-term count. ** The visitation reward is the state-action count at the current time, i.e.,  
\[r^{W}_{t}= \begin{cases}n(s_{t},a_{t})&\text{if $s_{t}$ is non-terminal}\\ \frac{1}{1-\gamma_{w}}n(s_{t},a_{t})&\text{otherwise}.\end{cases}  \tag{15}\]  
This W-function represents the discount-weighted average count along the trajectory, i.e.,  
\[W^{\beta}_{s}(s_{t},a_{t})=\sum_{i=t}^{H}\gamma_{w}^{i-t}n(s_{i},a_{i}), \tag{16}\]  
and its TD error is  
\[\delta^{W}(s_{t},a_{t},s_{t+1})= \begin{cases}r^{W}_{t}+\gamma_{w}\min_{a}W^{ \beta}_{s,i}(s_{t+1},a)-W^{\beta}_{s,i}(s_{t},a_{t})&\text{if $s_{t}$ is non-terminal}\\ r^{W}_{t}-W^{\beta}_{s,i}(s_{t},a_{t})&\text{otherwise}.\end{cases}