# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 4 Evaluation
### Part 2: In-Depth Investigation
#### 4.2.5 Stochastic Gridworlds  
As we discussed in Section 3.4, the visitation rewards for training the W-functions penalize terminal state-action pairs. One may think that this would lead to poor exploration in stochastic environments, where the same state-action pair can lead to both terminal and non-terminal states. Here, we evaluate all algorithms again on some of the previous environments but this time with stochastic transitions and show that our W-functions still solve the MDPs and outperform existing algorithms. Each transition \((s,a)\) has probability \(p\) of succeeding, \(1-p/2\) of not moving the agent, and \(1-p/2\) of moving the agent to a random adjacent state. In our experiments, we set \(p=0.9\). Due to the stochasticity of transitions, we increased the number of random seeds from 20 to 50.  
Figure 26: **Sample complexity against \(\varepsilon\), and MSVE over time for 27- and 55-state chainworlds. Shaded areas denote 95% confidence interval. As shown in Figure 25, the sample complexity of our approach is barely influenced by \(\varepsilon\). Even for \(\varepsilon=0\), our algorithms attain low sample complexity, whereas other algorithms complexity is several orders of magnitude higher. Similarly, only our algorithms learn an almost perfect Q-function, achieving an MSVE close to zero.**  
Figure 25: **Sample complexity on varying the chain size \(N=5,7\ldots,59\). Error bars denote 95% confidence interval. Only the proposed algorithms (blue and orange lines almost overlap) show little sensitivity to \(\varepsilon\), as their sample complexity only slightly increases as \(\varepsilon\) decreases. By contrast, other algorithms are highly influenced by \(\varepsilon\). Their estimate complexity has a large confidence interval, and for smaller \(\varepsilon\) they rarely learn an \(\varepsilon\)-optimal policy.**  
Figure 27 shows the number of states discovered and the expected discounted return computed in closed form as \(V^{\pi}(s_{0})\), where \(V^{\pi}\) is defined according to the Bellman expectation equation \(V^{\pi}=(I-\gamma\mathcal{P}^{\pi})^{-1}R^{\pi}\). Similarly to the deterministic setting (Figures 12, 16 and 17, leftmost plots), our method (blue and orange) outperform all baselines, being the only solving all MPDs within the steps limit (because of the stochasticity we decreased the learning rate from 0.5 to 0.1, and increased the learning steps). With the UCB reward (blue), our approach always learns the optimal policy. With the count reward (orange), our approach almost always learns it, and converges to a distractor only two times (out of 50) in the deep gridworld, and once in the \"prison\" gridworld. However, they both quickly discovered all states, as shown by top plots. The better performance of the UCB-based reward is due to the optimistic initialization of the W-function. As seen in Section 4.2.4, Figure 24a, this version of the algorithm explores the environment for longer and converges to the greedy policy later. Therefore, the agent will visit the high-reward state more often, and it is less likely to learn suboptimal policies.  
Bootstrapping with a prior (green) is not affected by the stochasticity, and it performs as in the deterministic setting (it solves the \"toy\" gridworld but not the other two). Vanilla bootstrapping (red), instead, is heavily affected by the stochasticity, and its performance is substantially worse compared to the deterministic setting (it cannot learn even the \"toy\" gridworld within steps limit). UCB1 (brown) and bonus-based exploration (pink), instead, benefit from the stochasticity. In the deterministic setting they could not solve these MDPs, while here they solve the two gridworlds (even though much later than ours). This improvement is explained by the larger number of visited states (top plots), which denotes an overall better exploration. This is not surprising if we consider that a stochastic transition function naturally helps exploration.