# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 4 Evaluation
### Part 1: Discounted Return and States Discovered
#### 4.1.4 Gridworlds  
In these environments (Figures 13-15), the agent navigates in a grid. Black cells cannot be visited, while any action in the prison has only an arbitrarily small probability of success. If it fails, the agent does not move. In practice, the prison almost completely prevents exploration. The reward is \(0\) everywhere except in treasure or penalty cells and is given for executing an action in the state, i.e., on transitions. Treasure cells (denoted by a money bag or a green number) give a bonus reward of different magnitude and end the episode. Penalty cells (denoted by a red number) give a penalty reward and end the episode. The agent also gets a small penalty of \(-0.01\) at each step. The goal, thus, is to find the biggest treasure using as few steps as possible. The initial position is fixed such that it is far from the biggest treasure and close to the smallest one. Figure 12: **Results on the deep gridworld** averaged over 20 seeds. Once again, the proposed algorithms are the only solving the task without optimistic initialization. Figure 13: The “toy” gridworld. These domains are designed to highlight the difficulty of learning with many distractors (the smaller treasures) and, thus, of many local optima. The addition of the constant penalty at each step further discourages exploration and makes the distractors more appealing, since ending the episode will stop receiving penalties. Each domain has increasing difficulty and introduces additional challenges, as we explain below. We start with the **\"toy\" gridworld** (Figure 13), a simple \(5\times 5\) grid with one reward of value 1. The focus of this domain is learning with sparse reward, without distractors or additional difficulties. The optimal policy takes only nine steps to reach the treasure, and the \"short horizon\" scenario ends after eleven steps. **The \"prison\" gridworld** (Figure 14) increases the value of the furthest reward to 5, adds two distractors of value \(1\) and 2, and a prison cell. The first distractor is close to the initial position, while the second is close to the goal reward. The prison cell is close to the goal. The optimal policy navigates around the first distractor, then right below the prison, and finally up to the goal. The prison highlights the importance of seeking states with low long-term visitation count, rather than low immediate count. As discussed in Section 3.1, current count-based algorithms cannot deal with these kinds of states efficiently. Finally, **the \"wall\" gridworld** (Figure 15) has a larger grid size (\(50\times 50\)), more rewards and penalties, and a wall separating the grid into two areas. The first area, where the agent starts, has six small rewards and penalties. The second area has two bigger treasures in the upper-right and bottom-right corners, of value 500 and 10,000, respectively. The optimal policy brings the agent beyond the wall and then to the bottom right corner, where the highest reward lies. The wall significantly increases the difficulty, due to the narrow passage that the agent needs to find in order to visit the second area of the grid. Learning is even harder when the horizon is short, as the agent cannot afford to lose time randomly  
Figure 14: The “prison” gridworld. Figure 15: The “wall” gridworld. looking for new states. To increase the chance of success of all algorithms, we set the \"short horizon\" to 330 steps, and 135 are needed to reach the reward of 10,000. **Results. ** The gridworlds confirm previous results. Without distractors (toy gridworld, Figure 16), bootstrapped algorithms (green and red) perform well, and so does using the auxiliary visitation bonus (pink). Neither, however, match ours (blue and orange, almost overlapping). Increasing the horizon helps the remainder algorithms, including random exploration (light green), except for approximate Thompson sampling (purple). In the next gridworld, however, the distractors and the prison cell substantially harm all algorithms except ours (Figure 17).