# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 3 Long-Term Visitation Value for Deep Exploration
### Example of the Limitations of Existing Immediate Count Methods  
Consider the toy problem of an agent moving in a grid, shown in Figure 2. Reward is 0 everywhere except in \((1,1)\) and \((3,1)\), where it is 1 and 2, respectively. The reward is given for executing an action in the state, i.e., on transitions from reward states. The agent's initial position is fixed in \((1,3)\) and the episode ends when a reward is collected or after five steps. Any action in the prison cells \((2,2)\) has only an arbitrarily small probability of success. If it fails, the agent stays in \((2,2)\). In practice, the prison cell almost completely prevents any further exploration. Despite its simplicity, this domain highlights two important challenges for exploration in RL with sparse rewards. First, there is a locally optimal policy collecting the lesser reward, which acts as a distractor. Second, the prison state is particularly dangerous as it severely hinders exploration. Assume that the agent has already explored the environment for four episodes performing the following actions: (1) left, down, left, down, down (reward 1 collected); (2) up, down, right, right (fail), right (fail); (3) right, left, right, down, down (fail); (4) right, down, left (fail), up (fail), right (fail). The resulting state-action visitation count is shown in Figure 2(a). Given this data, we initialize \(Q^{\pi}(s,a)\) to zero, train it with Q-learning with \(\gamma=0.99\) until convergence, and then derive three greedy policies. The first simply maximizes \(Q^{\pi}(s,a)\). The second maximizes the behavior \(Q^{\beta}(s,a)\) based on UCB1 [28], defined as  
\[Q^{\beta}(s,a)=Q^{\pi}(s,a)+\kappa\sqrt{\frac{2\log\sum_{a}n(s_{t},a_{j})}{n(s _{t},a)}}, \tag{5}\]  
where \(n(s,a)\) is the state-action count, and \(\kappa\) is a scaling coefficient. Note that in classic UCB, the reward is usually bounded in \([0,1]\) and no coefficient is needed. This is not usually the case for MDPs, where Q-values can be larger/smaller than \(1/0\). We thus need to scale the square root with \(\kappa=(r_{\max}-r_{\min})/(1-\gamma)\), which upper-bounds the difference between the largest and smallest possible Q-value). The third maximizes an augmented Q-function \(Q^{+}(s,a)\) trained by adding the intrinsic reward based on the immediate count [30], i.e.,  
\[r_{t}^{+}=r_{t}+\alpha\,n(s_{t},a_{t})^{-1/2}, \tag{6}\]  
where \(\alpha\) is a scaling coefficient set to \(\alpha=0.1\) as in [15; 30]. Figure 2(a) shows the state-action count after the above trajectories, and Figure 2(b)-d depict the respective Q-functions (colormap) and policies (arrows). Given the state-action count, consider what the agent has done and knows so far. 1. It has executed all actions at least once in (1,3) and (2,2) (the prison cell),
2. It still did not execute \"up\" in (1,2),  
Figure 2: Toy problem domain. It visited (1,3) once and experienced the reward of 1, and
4. It still did not execute \"up\" and \"right\" in (2,1). In terms of exploration, the best decision would be to select new actions, such as \"up\" in (1,2). _However, what should the agent do in states where it has already executed all actions at least once? Ideally, it should select actions driving it to unvisited states, or to states where it has not executed all actions yet_. However, none of the policies above exhibits such behavior. 1. The greedy policy (Figure 3b) points to the only reward collected so far. 2. The UCB1 policy (Figure 3c) yields Q-values of much larger magnitude. Most of the actions have been executed a few times, thus their UCB is larger than their Q-value. The policy correctly selects unexecuted actions in (1,2) and (2,3) but fails (1,3). There, it also selects the least executed actions ('up\" and \"left\") which, however, have already been executed once. The agent should know that these actions do not bring it anywhere (the agent hits the environment boundaries and does not move) and should avoid them. However, it selects them because the policy \(Q^{\beta}(s,a)\) is based on the _immediate_ visitation count.