# Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning
## 4 Evaluation  
In this section, we evaluate the proposed method against state-of-the-art methods for exploration in model-free RL on several domains. The experiments are designed to highlight the challenges of learning with sparse rewards and are split into two parts. In the first, we present the environments and we address (1) learning when only a few states give a reward, (2) learning when a sequence of correct actions is needed to receive a reward, (3) exploring efficiently when few steps are allowed per training episode, (4) avoiding local optima and distracting rewards, and (5) avoiding dangerous states that stop the agent preventing exploration. In the second, we further investigate (6) the visitation count at convergence, (7) the empirical sample complexity, (8) the impact of the visitation value hyperparameter \(\gamma_{w}\), (9) the performance in the infinite horizon scenario, and (10) with stochastic transition function.  
To ensure reproducibility, the experiments are performed over 20 and 50 fixed random seeds, for deterministic and stochastic MDPs, respectively. Pseudocode and further details of the hyperparameters are given in Appendix A. The source code is available at [[https://github.com/sparisi/visit-value-explore](https://github.com/sparisi/visit-value-explore)]([https://github.com/sparisi/visit-value-explore](https://github.com/sparisi/visit-value-explore)), accessed on 20 January 2022.  
**Baseline Algorithms.** The evaluated algorithms all use Q-learning [22] and share the same hyperparameters, e.g., learning rate and discount factor. In most of the experiments, we use infinite replay memory as presented by [PERSON] et al. [4]. In Appendix A.6 we also present an evaluation without replay memory on some domains. The algorithms all learn two separate Q-tables, a behavior one for exploration, and a target one for testing the quality of the greedy policy. The difference among the algorithms is how the behavior policy performs exploration. In this regard, we compare against the following exploration strategies: random, \(\epsilon\)-greedy, bootstrapped, count-based.  
For bootstrapping, we evaluate the original version proposed by [PERSON] et al. [9], as well as the more recent versions of [PERSON] et al. [46] and [PERSON] et al. [4]. These methods share the same core idea, i.e., to use an ensemble of Q-tables, each initialized differently and trained on different samples, to approximate a distribution over Q-values via bootstrapping. The differences are the following. [PERSON] et al. [9] select a random Q-table at the beginning of the episode and use it until the episode is over. [PERSON] et al. [4] further regularize the Q-tables using the squared \(\ell_{2}\)-norm to \"prior tables\" representing a prior over the Q-function. [PERSON] et al. [46] select the Q-table randomly within the ensemble at each step to approximate [PERSON] sampling, but without any prior.  
For count-based algorithms, we compare against UCB1 exploration [28] on the immediate state-action count as in Equation (5), and against augmenting the reward with the exploration bonus proposed by [PERSON] and [PERSON] [30] as in Equation (6). Notice that [PERSON] and [PERSON] [30] apply the bonus to a model-based algorithm, but since then it has been used by many model-free algorithms [15; 17]. Some recent methods use other bonuses to derive strong convergence guarantees [16; 17]. However, for large-size problems, these methods may require an impractical number of samples and are outperformed by standard algorithms.