Count-Based Exploration in Feature Space for Reinforcement Learning

Introduction

Reinforcement learning (RL) methods have recently enjoyed widely publicised success in domains that once seemed far beyond their reach Mnih et al. (2015). Much of this progress is due to the application of modern function approximation techniques to the problem of policy evaluation for Markov Decision Processes (MDPs) Sutton and Barto (1998). These techniques address a key shortcoming of tabular MDP solution methods: their inability to generalise what is learnt from one context to another. This sort of generalisation is crucial if the state-action space of the MDP is large, because the agent typically only visits a small subset of that space during training.

Comparatively little progress has been made on the problem of efficient exploration in large domains. Even algorithms that use sophisticated nonlinear methods for policy evaluation tend to use very old, inefficient exploration techniques, such as the $\epsilon$-greedy strategy van Hasselt et al. (2016b); Mnih et al. (2016); Nair et al. (2015). There are more efficient tabular count-based exploration algorithms for finite MDPs, which drive the agent to reduce its uncertainty by visiting states that have low visit-counts Strehl and Littman (2008). However, these algorithms are often ineffective in MDPs with high-dimensional state-action spaces, because most states are never visited during training, and the visit-count remains at zero nearly everywhere.

Count-based exploration algorithms have only very recently been successfully adapted for these large problems Bellemare et al. (2016); Tang et al. (2016). Just as function approximation techniques achieve generalisation across the state space regarding value, these algorithms achieve generalisation regarding uncertainty. The breakthrough has been the development of generalised state visit-counts, which are larger for states that are more similar to visited states, and which can be nonzero for unvisited states. The key challenge is to compute an appropriate similarity measure in an efficient way, such that these exploration methods can be combined with scalable RL algorithms. It soon becomes infeasible, for example, to do so by storing the entire history of visited states and comparing each new state to those in the history. The most promising proposals instead compute generalised counts from a compressed representation of the history of visited states – for example, by constructing a visit-density model over the state space and deriving a “pseudocount” Bellemare et al. (2016); Ostrovski et al. (2017), or by using locality-sensitive hashing to cluster states and counting the occurrences in each cluster Tang et al. (2016).

This paper presents a new count-based exploration algorithm that is feasible in environments with large state-action spaces. It can be combined with any value-based RL algorithm that uses linear function approximation (LFA). Our principal contribution is a new method for computing generalised visit-counts. Following Bellemare et al. (2016), we construct a visit-density model in order to measure the similarity between states. Our approach departs from theirs in that we do not construct our density model over the raw state space. Instead, we exploit the feature map that is used for value function approximation, and construct a density model over the transformed feature space. This model assigns higher probability to state feature vectors that share features with visited states. Generalised visit-counts are then computed from these probabilities; states with frequently observed features are assigned higher counts. These counts serve as a measure of the uncertainty associated with a state. Exploration bonuses are then computed from these counts in order to encourage the agent to visit regions of the state-space with less familiar features.

Our density model can be trivially derived from any feature map used for LFA, regardless of the application domain, and requires little or no additional design. In contrast to existing algorithms, there is no need to perform a special dimensionality reduction of the state space in order to compute our generalised visit-counts. Our method uses the same lower-dimensional feature representation to estimate value and to estimate uncertainty. This makes it simpler to implement and less computationally expensive than some existing proposals. Our evaluation demonstrates that this simple approach achieves near state-of-the-art performance on high-dimensional RL benchmarks.

Background and Related Work

2 Count-Based Exploration and Optimism

Since the true transition and reward distributions $\mathcal{P}$ and $\mathcal{R}$ are unknown to the agent, it must explore the environment to gather more information and reduce its uncertainty. At the same time, it must exploit its current information to maximise expected cumulative reward. This tradeoff between exploration and exploitation is a fundamental problem in RL.

Many of the exploration algorithms that enjoy strong theoretical guarantees implement the ‘optimism in the face of uncertainty’ (OFU) heuristic Strehl et al. (2009). Most are tabular and count-based in that they compute exploration bonuses from a table of state(-action) visit counts. These bonuses are added to the estimated state/action value. Lower counts entail higher bonuses, so the agent is effectively optimistic about the value of less frequently visited regions of the environment. OFU algorithms are more efficient than random strategies like $\epsilon$-greedy because the agent avoids actions that yield neither large rewards nor large reductions in uncertainty Osband et al. (2016b).

3 Exploration in Large MDPs

Several very recent extensions of count-based exploration methods have produced impressive results on high-dimensional RL benchmarks. These algorithms closely resemble MBIE-EB, but they substitute the state-action visit-count for a generalised count which quantifies the similarity of a state to previously visited states. Bellemare et. al. construct a Context Tree Switching (CTS) density model over the state space such that higher probability is assigned to states that are more similar to visited states Bellemare et al. (2016); Veness et al. (2012). A state pseudocount is then derived from this density. A subsequent extension of this work replaces the CTS density model with a neural network Ostrovski et al. (2017). Another recent proposal uses locality sensitive hashing (LSH) to cluster similar states, and the number of visited states in a cluster serves as a generalised visit-count Tang et al. (2016). As in the MBIE-EB algorithm, these counts are used to compute exploration bonuses. These three algorithms outperform random strategies, and are currently the leading exploration methods in large discrete domains where exploration is hard.

Method

Here we introduce the $\phi$-Exploration Bonus ($\phi$-EB) algorithm, which drives the agent to visit states about which it is uncertain. Following other optimistic count-based exploration algorithms, we use a (generalised) state visit-count in order to estimate the uncertainty associated with a state. A generalised count is a novelty measure that quantifies how dissimilar a state is from those already visited. Measuring novelty therefore involves choosing a similarity measure for states. Of course, states can be similar in myriad ways, but not all of these are relevant to solving the MDP. If the solution method used is value-based, then states should only be considered similar if they share the features that are determinative of value. This motivates us to construct a similarity measure that exploits the feature representation that is used for value function approximation. These features are explicitly designed to be relevant for estimating value. If they were not, they would not permit a good approximation to the true value function. This sets our method apart from the approaches described in section 2.3. They measure novelty with respect to a separate, exploration-specific representation of the state space, one that bears no relation to the value function or the reward structure of the MDP. We argue that measuring novelty in feature space is a simpler and more principled approach, and hypothesise that more efficient exploration will result.

Our exploration method is designed for use with LFA, and measures novelty with respect to a fixed feature representation of the state space. The challenge is to measure novelty without computing the distance between each new feature vector and those in the history. That approach becomes infeasible because the cost of computing these distances grows with the size of the history.

Let $\rho:\mathcal{T}^{*}\times\mathcal{T}\to$ be a density model that maps a finite sequence of feature vectors $\bm{\phi}_{1:t}\in\mathcal{T}^{*}$ to a probability distribution over $\mathcal{T}$. The feature visit-density $\rho_{t}(\bm{\phi})$ at time $t$ is the distribution over $\mathcal{T}$ that is returned by $\rho$ after observing $\bm{\phi}_{1:t}$.

If $\mathcal{U}$ is countable we can use a count-based estimator for the factor models $\rho_{t}^{i}(\phi_{i})$, such as the empirical estimator $\rho_{t}^{i}(\phi_{i})=\frac{N_{t}(\phi_{i})}{t}$, where $N_{t}(\phi_{i})$ is the number of times $\phi_{i}$ has occurred. In our implementation we use the Krichevsky-Trofimov (KT) estimator $\rho_{t}^{i}(\phi_{i})=\frac{N_{t}(\phi_{i})+\frac{1}{2}}{t+1}$.

This density model induces a similarity measure on the feature space. Loosely speaking, feature vectors that share component features are deemed similar. This enables us to use $\rho_{t}(\bm{\phi})$ as a novelty measure for states, by comparing the features of newly observed states to those in the history. If $\bm{\phi}(s)$ has more novel component features, $\rho_{t}(\bm{\phi})$ will be lower. By modelling the features as independent, and using count-based estimators as factor models, our method learns reasonable novelty estimates from very little data.

Suppose we use a 3-D binary feature map and that after 3 timesteps the history of observed feature vectors is $\bm{\phi}_{1:3}=(0,1,0),(0,1,0),(0,1,0)$. Let us estimate the feature visit densities of two unobserved feature vectors $\bm{\phi^{\prime}}=(1,1,0)$, and $\bm{\phi}^{\prime\prime}=(1,0,1)$. Using the KT estimator for the factor models, we have $\rho_{3}(\bm{\phi}^{\prime})=\rho_{3}^{1}(1)\cdot\rho_{3}^{2}(1)\cdot\rho_{3}^{3}(0)=\frac{1}{8}\cdot\frac{7}{8}\cdot\frac{7}{8}\approx 0.1$, and $\rho_{3}(\bm{\phi}^{\prime\prime})=\rho_{3}^{1}(1)\cdot\rho_{3}^{2}(0)\cdot\rho_{3}^{3}(1)=(\frac{1}{8})^{3}\approx 0.002$. Note that $\rho_{3}(\bm{\phi}^{\prime})>\rho_{3}(\bm{\phi}^{\prime\prime})$ because the component features of $\bm{\phi}^{\prime}$ are more similar to those in the history. As desired, our novelty measure generalises across the state space.

2 The ϕitalic-ϕ\phi-pseudocount

Here we adopt a recently proposed method for computing generalised visit-counts from density models Bellemare et al. (2016); Ostrovski et al. (2017). By analogy with these pseudocounts, we derive two $\phi$-pseudocounts from our feature visit-density.

Let $\rho_{t}(\bm{\phi})$ be the feature visit-density after observing $\bm{\phi}_{1:t}$. Let $\rho^{\prime}_{t}(\bm{\phi})$ denote the same density model after $\bm{\phi}_{1:t}\bm{\phi}$ has been observed.

The $\phi$-pseudocount $\hat{N}_{t}^{\phi}(s)$ for a state $s\in\mathcal{S}$ at time $t$ is

3 Reinforcement Learning with ϕitalic-ϕ\phi-EB

Following traditional count-based exploration algorithms, we drive optimistic exploration by computing a bonus from the $\phi$-pseudocount.

As in the MBIE-EB algorithm, this bonus is added to the reward $r_{t}$. The agent is trained on the augmented reward $r_{t}^{+}=r_{t}+R_{t}^{\phi}(s,a)$ using any value-based RL algorithm with LFA. At each timestep our algorithm performs updates for at most $M$ estimators, one for each feature. The cost of our method is therefore independent of the size of the state-action space, and scales only in the number of features. If the feature vectors are sparse, we can maintain a single prototype estimator for all the features that have not yet been observed. Under these conditions our method scales only in the number of observed features.

Theoretical Results

Let $\bm{\phi},\bm{\phi^{\prime}}\in\{0,1\}^{M}$ be $M$-length binary vectors. The Hamming similarity between $\bm{\phi}$ and $\bm{\phi^{\prime}}$ is $\mbox{Sim}(\bm{\phi},\bm{\phi^{\prime}})=1-\frac{1}{M}\left\|\bm{\phi}\bm{-\phi^{\prime}}\right\|_{1}$.

Note that $\mbox{Sim}(\bm{\phi},\bm{\phi^{\prime}})\in$ for all $\bm{\phi},\bm{\phi^{\prime}}\in\{0,1\}^{M}$. The Hamming similarity is large if $\bm{\phi}$ and $\bm{\phi^{\prime}}$ share features (i.e. if the $l_{1}$-distance between them is small). We now prove a lemma relating the joint probability of a feature vector to the sum of the probabilities of its factors.

Let $\bm{\phi}\in\{0,1\}^{M}$, and let \rho_{t}(\mbox{\bm{\phi}})=\prod_{i=1}^{M}\rho_{t}^{i}(\phi_{i}). Then $\sqrt{\rho(\bm{\phi})}\leq\frac{1}{M}\sum_{i=1}^{M}\rho_{t}^{i}(\phi_{i})$.

By the inequality of arithmetic and geometric means $\sqrt{\rho(\bm{\phi})}=\sqrt{\prod_{i=1}^{M}\rho_{t}^{i}(\phi_{i})}\leq\sqrt[M]{\prod_{i=1}^{M}\rho_{t}^{i}(\phi_{i})}\leq\frac{1}{M}\sum_{i=1}^{M}\rho_{t}^{i}(\phi_{i})$ ∎

The following lemma relates the probability of an individual feature to its $l_{1}$-distance from previously observed values.

Let $\rho_{t}^{i}(\phi_{i})=\frac{1}{t}N_{t}(\phi_{i})$. Then for all $\phi_{i},\phi_{k,i}\in\{0,1\}$, $\rho_{t}^{i}(\phi_{i})=\frac{1}{t}\sum_{k=1}^{t}1-\left|\phi_{i}-\phi_{k,i}\right|$.

The $\phi_{i}=1$ case follows by an almost identical argument. ∎

The following theorem and its corollary are the major results of this section. These connect the Hamming similarity (to previously observed feature vectors) with both the feature visit-density and the $\phi$-pseudocount. We show that a state which shares few features with those in the history will be assigned low probability by our density model, and will therefore have a low $\phi$-pseudocount.

Let $s\in\mathcal{S}$ be a state with binary feature representation $\bm{\phi}=\bm{\phi}(s)\in\{0,1\}^{M}$, and let $\rho_{t}(\bm{\phi})=\prod_{i=1}^{M}\rho_{t}^{i}(\phi_{i})$ be its feature visit-density at time $t$. Then

where (a) follows from Lemma 1, (b) from Lemma 2, and (c) from Definition 4. ∎

Immediate from Theorem 1 and Definition 2. ∎

Empirical Evaluation

Our evaluation is designed to answer the following research questions:

Is a novelty measure derived from the features used for LFA a good way to generalise state visit-counts?

Does $\phi$-EB produce improvement across a range of environments, or only if rewards are sparse?

Can $\phi$-EB with LFA compete with the state-of-the-art in exploration and deep RL?

We evaluate our algorithm on five games from the Arcade Learning Environment (ALE), which has recently become a standard high-dimensional benchmark for RL Bellemare et al. (2013). The reward signal is computed from the game score. The raw state is a frame of video (a 160$\times$210 array of 7-bit pixels). There are 18 available actions. The ALE is a particularly interesting testbed in our context, because the difficulty of exploration varies greatly between games. Random strategies often work well, and it is in these games that Deep Q-Networks (DQN) with $\epsilon$-greedy is able to achieve so-called human-level performance Mnih et al. (2015). In others, however, DQN with $\epsilon$-greedy does not improve upon a random policy, and its inability to explore efficiently is one of the key determinants of this failure Osband et al. (2016a). We chose five of these games where exploration is hard. Three of the chosen games have sparse rewards (Montezuma’s Revenge, Venture, Freeway) and two have dense rewards (Frostbite, Q*bert).Note that our experimental evaluation uses the stochastic version of the ALE Bellemare et al. (2013).

Evaluating agents in the ALE is computationally demanding. We chose to focus more resources on Montezuma’s Revenge and Venture, for two reasons: (1) we hypothesise that $\phi$-EB will produce more improvement in sparse reward games, and (2) leading algorithms with which we seek to compare $\phi$-EB have also focused on these games. We conducted five independent learning trials for Montezuma and Venture, and two trials for the remaining three games. All agents were trained for 100 million frames on the no-op metric Bellemare et al. (2013). Trained agents were then evaluated for 500 episodes; Table 1 reports the average evaluation score.

We implement Algorithm 1 using Sarsa($\lambda$) with replacing traces and LFA as our RL method, because it is less likely to diverge than $Q$-learning Sutton and Barto (1998). To implement LFA in the ALE we use the Blob-PROST feature set presented in Liang et al. (2016). To date this is the best performing feature set for LFA in the ALE. The parameters for the Sarsa($\lambda)$ algorithm are set to the same values as in Liang et al. (2016). Hereafter we refer to our algorithm as Sarsa-$\phi$-EB. To conduct a controlled investigation of the effectiveness of $\phi$-EB, we also evaluate a baseline implementation of Sarsa($\lambda$) with the same features but with $\epsilon$-greedy exploration (which we denote Sarsa-$\epsilon$). The same training and evaluation regime is used for both; learning curves are reported in Figure 1.

The $\beta$ coefficient in the $\phi$-exploration bonus was set to 0.05 for all games, after a coarse parameter search. This search was performed once, across a range of ALE games, and a value was chosen for which the agent achieved good scores in most games.

2 Results

In Montezuma’s Revenge, Sarsa-$\epsilon$ rarely leaves the first room. Its policy converges after an average of 20 million frames. Sarsa-$\phi$-EB continues to improve throughout training, visiting up to 14 rooms. The largest improvement over the baseline occurs in Venture. Sarsa-$\epsilon$ fails to score, while Sarsa-$\phi$-EB continues to improve throughout training. In Q*bert and Frostbite, the difference is less dramatic. These games have dense, well-shaped rewards that guide the agent’s path through state space and elide $\epsilon$-greedy’s inefficiency. Nonetheless, Sarsa-$\phi$-EB consistently outperforms Sarsa-$\epsilon$ throughout training so its cumulative reward is much higher.

In Freeway, Sarsa-$\phi$-EB with $\beta=0.05$ fails to match the performance of the baseline algorithm, but with $\beta=0.035$ it performs better (Figure 1 shows the learning curve for the latter). This sensitivity to the $\beta$ parameter likely results from the large number of unique Blob-PROST features that are active in Freeway, many of which are not relevant for finding the optimal policy. If $\beta$ is too high the agent is content to stand still and receive exploration bonuses for observing new configurations of traffic. This accords with our hypothesis that efficient optimistic exploration should involve measuring novelty with respect to task-relevant features.

In summary, Sarsa-$\phi$-EB with $\beta=0.05$ outperforms Sarsa-$\epsilon$ on all tested games except Freeway. Since both use the same feature set and RL algorithm, and differ only in their exploration policies, this is strong evidence that $\phi$-EB produces improvement over random exploration across a range of environments. This also supports our conjecture that using the same features for value function approximation and novelty estimation is an appropriate way to generalise visit-counts to the high-dimensional setting.

Comparison with Leading Algorithms

Table 1 compares our evaluation scores to Double DQN (DDQN) van Hasselt et al. (2016b), Double DQN with pseudocount (DDQN-PC) Bellemare et al. (2016), A3C+ Bellemare et al. (2016), DQN Pop-Art (DQN-PA) van Hasselt et al. (2016a), Dueling Network (Dueling) Wang et al. (2016), Gorila Nair et al. (2015), DQN with Model Prediction Exploration Bonuses (MP-EB) Stadie et al. (2015), Trust Region Policy Optimisation (TRPO) Schulman et al. (2015), and TRPO-AE-SimHash (TRPO-Hash) Tang et al. (2016). The most interesting comparisons for our purposes are with TRPO-Hash, DDQN-PC, A3C+, and MP-EB, because these algorithms all use exploration strategies that drive the agent to reduce its uncertainty. TRPO-Hash, DDQN-PC, and A3C+ are count-based methods, MP-EB seeks high model prediction error.

Our Sarsa-$\phi$-EB algorithm achieves an average score of 2745.4 on Montezuma: the second highest reported score. On this game it far outperforms every algorithm apart from DDQN-PC, despite only having trained for half the number of frames. Note that neither A3C+ nor TRPO-Hash achieves more than 200 points, despite their exploration strategies.

On Venture Sarsa-$\phi$-EB also achieves state-of-the-art performance. It achieves the third highest reported score despite its short training regime, and far outperforms A3C+ and TRPO-Hash. DDQN-PC evaluation scores are not given for Venture, but reported learning curves suggest Sarsa-$\phi$-EB performs much better here Bellemare et al. (2016). The performance of Sarsa-$\phi$-EB in Frostbite also seems competitive given the shorter training regime. Nonlinear algorithms perform better in Q*bert. In Freeway Sarsa-$\phi$-EB fails to score any points, for reasons already discussed.

Conclusion

We have introduced the $\phi$-Exploration Bonus method, a count-based optimistic exploration strategy that scales to high-dimensional environments. It is simpler to implement and less computationally demanding than some other proposals. Our evaluation shows that it improves upon $\epsilon$-greedy exploration on a variety of games, and that it is even competitive with leading exploration techniques developed for deep RL. Unlike other methods, it does not require the design of an exploration-specific state representation, but rather exploits the features used in the approximate value function. We have argued that computing novelty with respect to these task-relevant features is an efficient and principled way to generalise visit-counts for exploration. We conclude by noting that this reliance on the feature representation used for LFA is also a limitation. It is not obvious how a method like ours could be combined with the nonlinear function approximation techniques that have driven recent progress in RL. We hope the success of our simple method will inspire future work in this direction.

References