# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 4 Evaluation
### Part 2: In-Depth Investigation
#### 4.2.4 Infinite Horizon Stochastic Chainworld  
This evaluation investigates how the algorithms perform in a stochastic MDP with infinite horizon. In particular, we are interested in (1) the mean squared value error (MSVE) at each timestep, (2) the sample complexity when varying the number of states, and (3) how behavior policies explore and if they converge to the greedy policy. **Evaluation Criteria. ** The MSVE is computed between the true value function of the optimal policy \(V^{*}(s)\) and the learned value function of the current policy \(V^{\pi_{t}}(s)\), i.e.,  
\[\text{MSVE}=\frac{1}{N}\sum_{i=1}^{N}{(V^{*}(s_{i})-V^{\pi_{t}}(s))^{2}}. \tag{30}\]  
The value function is computed according to the Bellman expectation equation in matrix form, i.e., \(V^{\pi}=(I-\gamma\mathcal{P}^{\pi})^{-1}R^{\pi}\), where \(I\) is the identity matrix, and \(\mathcal{P}^{\pi}\) and \(R^{\pi}\) are the transition and reward functions induced by the policy, respectively, [56]. This error indicates how much the learned greedy policy \(\pi_{t}\) deviates from the optimal policy. Similarly, the sample complexity is defined as the number of timesteps \(t\) such that the non-stationary policy \(\pi_{t}\) at time \(t\) is not \(\varepsilon\)-optimal for current state \(s_{t}\), i.e., \(V^{*}(s_{t})-V^{\pi_{t}}(s_{t})>\varepsilon\)[17; 30]. For the behavior of exploration policies and their empirical convergence, we show how the visitation count changes over time. **MDP Characteristics. ** The MDP, shown in Figure 23, is a chainworld with \(s=1,\dots,N\) states, three actions, and stochastic transition defined as follows. The first action moves the agent forward with probability \(p\), backward otherwise. The second action moves the agent backward with probability \(p\), forward otherwise. The third action keeps the agent in the current state with probability \(p\), and randomly moves it backward or forward otherwise. The initial state is the leftmost state, and no state is terminal. This MDP is ergodic, i.e., all states are transient, positive recurrent, and aperiodic for any deterministic policy. In our experiments, we set \(p=0.99\). The reward is \(10^{-8}\) for doing \"stay\" in the initial state \(s_{1}\), 1 for doing \"stay\" in the last state \(s_{N}\), and 0 everywhere else. Figure 22: **Steps to learn on varying the deep sea size \(N=5,7,\dots,59\), averaged over ten runs with 500,000 steps limit. For filled dots, the run always converged, and we report the 95% confidence interval with error bars. For empty dots connected with dashed lines, the algorithm did not learn within the step limit at least once. In this case, the average is over converged runs only and we do not report any confidence interval. Using the exploration bonus (pink) learning barely converged once (most of its dots are either missing or empty). Using bootstrapping (red) all runs converged, but the results show a large confidence interval. With random prior (green) the learning rarely did not converge, and performed very similarly across the random seeds, as shown by its extremely small confidence interval. On the contrary, our method (blue, orange) is the only always converging with a confidence interval close to zero. Indeed, it outperforms all baseline by attaining the lowest sample complexity. Missing algorithms (random, \(\varepsilon\)-greedy, UCB1, [PERSON] sampling) performed poorly and are not reported. **Unlike previous MDPs, this has no terminal state, the horizon is infinite, and the state is never reset. Instead, to simulate infinite horizon, the agent explores the environment for one episode of 200,000 steps. To comply with the classic sample complexity definition [17; 30], we use classic Q-learning without replay memory. We do not compare against bootstrapping algorithms, because they are designed to select a different behavior Q-function at every episode, and this setup has only one episode. Approximate [PERSON] sampling by [PERSON] et al.