# 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
Following Equation (19), we need to ensure that  
\[Q_{\min}+\kappa U_{W}(s,\bar{a}) >Q_{\max}+\kappa U_{W}(s,a),\] \[U_{W}(s,\bar{a}) >\frac{Q_{\max}-Q_{\min}}{\kappa}+U_{W}(s,a). \tag{25}\]  
However, here assuming uniform count does not guarantee a uniform _pseudocount_, i.e.,  
\[\forall(s,a)\
eq(s,\bar{a}),\quad n(s,a)=\bar{n}(s)\
Rightarrow W(s,\bar{a}) \geq W(s,a). \tag{26}\]  
To illustrate this issue, consider the chain MDP in \[\forall(s,a)\
eq(s,\bar{a}),\ \ \ n(s,a)=\bar{n}(s)\Rightarrow W(s,\bar{a}) \geq W(s,a). \tag{21}\]0 The agent always starts in \(A\) and can move left, right, and down. The episode ends after eight steps, or when terminal state \(E\) is reached. The goal of this example is to explore all states uniformly. In the first episode, the agent follows the blue trajectory \((A,D,E)\). In the second episode, it follows the red trajectory \((A,C,D,D,C,B,B,B)\). In both trajectories, an action with count zero was always selected first. At the beginning of the third episode, all state-action pairs have been executed once, except for \"left\" in \(A\), i.e., \(n(s,a)=1\)\(\forall(s,a)\
eq(A,left)\), \(n(A,left)=0\). Thus, we need to enforce the agent to select it. However, the discounted _cumulative_ count \(\hat{n}(s,a)=(1-\gamma_{w})W(s,a)\) is _not_ uniform. For example, with \(\gamma_{w}=0.9\), \(\hat{n}(A,right)=3.8\) and \(\hat{n}(A,down)=4.52\). More in general, the worst-case scenario for satisfying Equation (25) is the one where (1) action \(\bar{a}\) has not been executed yet, (2) an action \(\dot{a}\) has been executed once and has the smallest pseudocount, and (3) all other actions have been executed once and have the highest pseudocount. In this scenario, to select \(\bar{a}\) we need to guarantee \(U_{W}(s,\bar{a})>U_{W}(s,\bar{a})\). Assuming that counts are uniform and no action has been executed twice, the smallest pseudocount is \(\hat{n}(s,\dot{a})=1-\gamma_{w}\), while the highest is 1. Then, Equation (25) becomes  
\[\forall(s,a)\
eq(s,\bar{a}),\ \ \ n(s,a)=\bar{n}(s)\Rightarrow W(s,\bar{a}) \geq W(s,a). \tag{21}\]1 \[\forall(s,a)\
eq(s,\bar{a}),\ \ \ n(s,a)=\bar{n}(s)\Rightarrow W(s,\bar{a}) \geq W(s,a). \tag{21}\]2  
Replacing \(U_{W}(s,a)\) in Equation (19) with Equation (27) when \(n(s,\bar{a})=0\) guarantees to select \(\bar{a}\). **Example of exploration behavior under uniform count. ** Consider our toy problem again. This time, all state-action pairs have been executed once except for \"left\" in (1,3). The Q-table is optimal for visited state-action pairs, thus the greedy policy simply brings the agent to (3,1) where the highest reward lies. Figure 6 shows baseline and proposed  
\[\forall(s,a)\
eq(s,\bar{a}),\ \ \ n(s,a)=\bar{n}(s)\Rightarrow W(s,\bar{a}) \geq W(s,a). \tag{21}\]3 Chainworld with uniform count. behavior policies in two scenarios, depending on whether reward states are terminal (upper row) or not (bottom row). 1. The augmented reward policy (Figure 6b) has no interest in trying \"left\" in (1,3), and its value is the lowest. The agent, in fact, cannot get the visitation bonus without first executing the action. This shows once more that this passive way of exploration is highly inefficient. 2. UCB1 policy (Figure 6c) acts greedily everywhere except in (1,3), where it correctly selects the unexecuted action. However, since UCB1 considers only the _immediate_ visitation, it has no way of propagating this information to other state-action pairs. 3. By contrast, for the proposed W-function policies (Figure 6d,e) the unexecuted state-action pair is the most interesting, and, from any state, the policy brings the agent there. Thanks to the separate W-function, we can propagate the value of unexecuted actions to other states, always prioritizing the exploration of new state-action pairs. Under uniform count \(n(s,a)=1\;\forall(s,a)\), then the agent acts greedily w.r.t. the Q-function. Finally, if the count is uniform for all state-action pairs, including for \"left\" in (1,3), then all policies look like the greedy one (Figure 6a).