# 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  
Despite its simplicity, the above toy problem highlights the limitations of current exploration strategies based on the immediate count. More specifically, (1) considering the immediate count may result in shallow exploration, and (2) directly augmenting the reward to train the Q-function, i.e., coupling exploration and exploitation, can have undesired effects due to the non-stationarity of the augmented reward function. To address these limitations, we propose an approach that (1) plans exploration actions far into the future by using a _long-term visitation count_, and (2) decouples exploration and exploitation by  
Figure 3: **Toy example (part 1). Visitation count (a) and behavior policies (b–d) for the toy problem below. Cells are divided into four triangles, each one representing the count (a) or the behavior Q-value (b–d) for the actions ”up/down/left/right 1” in that cell. Arrows denote the action with the highest Q-value. None of the behavior policies exhibits long-term deep exploration. In (1,3) both UCB1 (c) and the augmented Q-table (d) myopically select the action with the smallest immediate count. The latter also acts badly in (1,2) and (2,3). There, it selects “left” which has count one, instead of “up” which has count zero. **  
learning a separate function assessing the _exploration value_ of the actions. Contrary to existing methods that use models of reward and dynamics [13], which can be hard to come by, our approach is off-policy and model-free. **Visitation value. ** The key idea of our approach is to train a visitation value function using the temporal difference principle. The function, called W-function and denoted by \(W^{\beta}(s,a)\), approximates the cumulative sum of an intrinsic reward \(r^{W}\) based on the visitation count, i.e.,  
\[W^{\beta}(s_{t},a_{t}):=\mathbb{E}_{\prod_{i\to t}\beta(a_{t+1}|s_{t+1}) \mathcal{P}(s_{i+1}|s_{i};a_{t})}\left[\sum_{i=t}^{H}\gamma_{w}^{i-t}r_{i}^{W} \right], \tag{7}\]  
where \(\gamma_{w}\) is the visitation count discount factor. The higher the discount, the more in the future the visitation count will look. In practice, we estimate \(W^{\beta}(s,a)\) using TD learning on the samples produced using the behavior policy \(\beta\). Therefore, we use the following update  
\[W^{\beta}_{i+1}(s_{t},a_{t})=W^{\beta}_{i}(s_{t},a_{t})+\eta\delta^{W}(s_{t},a _{t},s_{t+1}), \tag{8}\]  
where \(\eta\) is the learning rate, and \(\delta^{W}(s_{t},a_{t},s_{t+1})\) is the W-function TD error, which depends on the reward \(r^{W}\) (can be either maximized or minimized). Subsequently, following the well-known upper confidence bound (UCB) algorithm [25], the behavior policy is greedy w.r.t. the sum of the Q-function and upper confidence bound, i.e.,  
\[\beta(a|s)=\arg\max_{a}\{Q^{\pi}(s,a)+\kappa U_{W}(s,a)\}, \tag{9}\]  
where \(U_{W}(s,a)\) is an upper confidence bound based on \(W^{\beta}(s,a)\), and \(\kappa\) is the same exploration constant used by UCB1 in Equation (5). This proposed approach (1) considers long-term visitation count by employing the W-function, which is trained to maximize the cumulative--not the immediate--count. Intuitively, the W-function encourages the agent to explore state-actions that have not been visited before. Given the current state \(s\), in fact, \(W^{\beta}(s,a)\) specifies how much exploration we can expect on (discount-weighted) average in future states if we choose action \(a\). Furthermore, since the Q-function is still trained greedily w.r.t. the extrinsic reward as in Q-learning, while the W-function is trained greedily on the intrinsic reward and favors less-visited states, our approach (2) effectively decouples exploration and exploitation. This allows us to more efficiently prevent underestimation of the visitation count exploration term. Below, we propose two versions of this approach based on two different rewards \(r^{W}\) and upper bounds \(U_{W}(s,a)\). **W-function as long-term UCB.