Title: COUNT-BASED EXPLORATION WITH THE SUCCESSOR REPRESENTATION

Abstract: The problem of exploration in reinforcement learning is well-understood in the tabular case and many sample-efficient algorithms are known. Nevertheless, it is often unclear how the algorithms in the tabular setting can be extended to tasks with large state-spaces where generalization is required. Recent promising developments generally depend on problem-specific density models or handcrafted features. In this paper we introduce a simple approach for exploration that allows us to develop theoretically justified algorithms in the tabular case but that also give us intuitions for new algorithms applicable to settings where function approximation is required. Our approach and its underlying theory is based on the substochastic successor representation, a concept we develop here. While the traditional successor representation is a representation that defines state generalization by the similarity of successor states, the substochastic successor representation is also able to implicitly count the number of times each state (or feature) has been observed. This extension connects two until now disjoint areas of research. We show in traditional tabular domains (RiverSwim and SixArms) that our algorithm empirically performs as well as other sample-efficient algorithms. We then describe a deep reinforcement learning algorithm inspired by these ideas and show that it matches the performance of recent pseudo-count-based methods in hard exploration Atari 2600 games.

1. INTRODUCTION:

Reinforcement learning (RL) tackles sequential decision making problems by formulating them as tasks where an agent must learn how to act optimally through trial and error interactions with the environment. The goal in these problems is to maximize the sum of the numerical reward signal observed at each time step. Because the actions taken by the agent influence not just the immediate reward but also the states and associated rewards in the future, sequential decision making problems require agents to deal with the trade-off between immediate and delayed rewards. Here we focus on the problem of exploration in RL, which aims to reduce the number of samples (i.e., interactions) an agent needs in order to learn to perform well in these tasks when the environment is initially unknown.

The sample efficiency of RL algorithms is largely dependent on how agents select exploratory actions. In order to learn the proper balance between immediate and delayed rewards agents need to navigate through the state space to learn about the outcome of different transitions. The number of samples an agent requires is related to how quickly it is able to explore the state-space. Surprisingly, the most common approach is to select exploratory actions uniformly at random, even in high-profile success stories of RL (e.g., Tesauro, 1995; Mnih et al., 2015) . Nevertheless, random exploration often fails in environments with sparse rewards, that is, environments where the agent observes a reward signal of value zero for the majority of states. 1In model-based approaches agents explicitly learn a model of the dynamics of the environment which they use to plan future actions. In this setting the problem of exploration is well understood. When all states can be enumerated and uniquely identified (tabular case), we have algorithms with proven sample complexity bounds on the maximum number of suboptimal actions an agent selects before converging to an -optimal policy (e.g., Brafman & Tennenholtz, 2002; Kearns & Singh, 2002; Strehl & Littman, 2008) . However, these approaches are not easily extended to large environments where it is intractable to enumerate all of the states. When using function approximation, the concept of state visitation is not helpful and learning useful models is by itself quite challenging.

Due to the difficulties in learning good models in large domains, model-free methods are much more popular. Instead of building an explicit model of the environment, they estimate state values directly from transition samples (state, action, reward, next state). Unfortunately, this approach makes systematic exploration much more challenging. Nevertheless, because model-free methods make up the majority of approaches scalable to large domains, practitioners often ignore the exploration challenges these methods pose and accept the high sample complexity of random exploration. Reward bonuses that promote exploration are one alternative to random walks (e.g., Bellemare et al., 2016; Martin et al., 2017) , but none such proposed solutions are widely adopted in the field.

In this paper we introduce an algorithm for exploration based on the successor representation (SR). The SR, originally introduced by Dayan (1993) , is a representation that generalizes between states using the similarity between their successors, i.e., the similarity between the states that follow the current state given the environment's dynamics and the agent's policy. The SR is defined for any problem, it can be learned through temporal-difference learning (Sutton, 1988) and, as we discuss below, it can also be seen as implicitly estimating the transition dynamics of the environment. Our approach is inspired by the substochastic successor representation (SSR), a concept we introduce here. The SSR is defined so that it implicitly counts state visitation, allowing us to use it to encourage exploration. This idea connects representation learning and exploration, two otherwise disjoint areas of research. The SSR allows us to derive an exploration bonus that when applied to model-based RL generates algorithms that perform as well as theoretically sample-efficient algorithms. Importantly, the intuition developed with the SSR assists us in the design of a model-free deep RL algorithm that achieves performance similar to pseudo-count-based methods in hard exploration Atari 2600 games (Bellemare et al., 2016; Ostrovski et al., 2017) .

2. PRELIMINARIES:

We consider an agent interacting with its environment in a sequential manner. Starting from a state S 0 ∈ S, at each step the agent takes an action A t ∈ A, to which the environment responds with a state S t+1 ∈ S according to a transition probability function p(s |s, a) = Pr(S t+1 = s |S t = s, A t = a), and with a reward signal R t+1 ∈ R, where r(s, a) indicates the expected reward for a transition from state s under action a, that is, r(s, a)

.

= E[R t |S t = s, A t = a].

The value of a state s when following a policy π, v π (s), is defined to be the expected sum of discounted rewards from that state:

v π (s) . = E π T k=t+1 γ k-t-1 R k S t = s

, with γ being the discount factor. When the transition probability function p and the reward function r are known, we can compute v π (s) recursively by solving the system of equations below (Bellman, 1957) :

v π (s) = a π(a|s) r(s, a) + γ s p(s |s, a)v π (s ) .

This equation can also be written in matrix form with v π , r ∈ R |S| and P π ∈ R |S|×|S| :

EQUATION

where P π is the state to state transition probability function induced by π, that is, P π (s, s ) = a π(a|s)p(s |s, a). Traditional model-based algorithms for RL work by learning estimates of the matrix P π and of the vector r and using them to estimate v π , for example by solving Equation 1. We use Pπ and r to denote empirical estimates of P π and r. Formally,

EQUATION

where r(i) denotes the i-th entry in the vector r, n(s, s ) is the number of times the transition s → s was observed, n(s) = s ∈S n(s, s ), and C(s, s ) is the sum of the rewards associated with the n(s, s ) transitions (we drop the action in the discussion to simplify notation).

Alternatively, in model-free RL, instead of estimating P π and r we estimate v π (s) directly from samples. We often use temporal-difference (TD) learning (Sutton, 1988) to update our estimates of v π (s), v(•), online:

v(S t ) ← v(S t ) + α R t+1 + γv(S t+1 ) -v(S t ) ,

(3) where α is the step-size parameter. Generalization is required in problems with large state spaces, where it is unfeasible to learn an individual value for each state. We do so by parametrizing v(s) with a set of weights θ. We write, given the weights θ, v(s; θ) ≈ v π (s) and q(s, a; θ) ≈ q π (s, a), where q π (s, a) = r(s, a) + γ s p(s |s, a)v π (s ). Model-free methods have performed well in problems with large state spaces, mainly due to the use of neural networks as function approximators (e.g., Mnih et al., 2015) .

Our algorithm is based on the successor representation (SR; Dayan, 1993) . The successor representation, with respect to a policy π, Ψ π , is defined as

Ψ π (s, s ) = E π,p ∞ t=0 γ t I{S t = s } S 0 = s ,

where we assume the sum is convergent with I denoting the indicator function. Dayan (1993) has shown that this expectation can be estimated from samples through TD learning. It also corresponds to the Neumann series of γP :

Ψ π = ∞ t=0 γ t (P π ) t = (I -γP π ) -1 . (4)

Notice that the SR is part of the solution when computing a value function: v π = Ψ π r (Equation 1).

We use Ψπ to denote the SR computed through Pπ , the approximation of P π .

The definition of the SR can also be extended to features. Successor features generalize the SR to the function approximation setting (Barreto et al., 2017) . We use the definition for the uncontrolled case in this paper. Importantly, the successor features can also be learned with TD learning. Definition 2.1 (Successor Features). For a given 0 ≤ γ < 1, policy π, and for a feature representation φ(s) ∈ R d , the successor features for a state s are:

ψ π (s) = E π,p ∞ t=0 γ t φ(S t ) S 0 = s .

Alternatively, in matrix form, Ψ π = ∞ t=0 γ t (P π ) t Φ = (I -γP π ) -1 Φ. Notice that this definition reduces to the SR in the tabular case, where Φ = I.

3. THE SUBSTOCHASTIC SUCCESSOR REPRESENTATION:

In this section we introduce the concept of the substochastic successor representation (SSR). The SSR is derived from an empirical transition matrix similar to Equation 2, but where each state incorporates a small (1/(n(s) + 1)) probability of terminating at that state, rather than transiting to a next state. As we will show, we can recover the visit counts n(s) through algebraic manipulation on the SSR.

While computing the SSR is usually impractical, we use it as inspiration in the design of a new deep reinforcement learning algorithm for exploration (Section 4). In a nutshell, we view the SSR as approximating the process of learning the SR from an uninformative initialization (i.e., the zero vector), and using a stochastic update rule. While this approximation is relatively coarse, we believe it gives qualitative justification to our use of the learned SR to guide exploration. To further this claim, we demonstrate that using the SSR in synthetic, tabular settings yields comparable performance to that of theoretically-derived exploration algorithms. Definition 3.1 (Substochastic Successor Representation). Let Pπ denote the substochastic matrix induced by the environment's dynamics and by the policy π such that Pπ (s |s) = n(s,s ) n(s)+1 . For a given 0 ≤ γ < 1, the substochastic successor representation, Ψπ , is defined as:

Ψπ = ∞ t=0 γ t Pπ t = (I -γ Pπ ) -1 .

The theorem below formalizes the idea that the 1 norm of the SSR implicitly counts state visitation.

Theorem 1. Let n(s) denote the number of times state s has been visited and let χ(s) = (1 + γ) -|| Ψπ (s)|| 1 , where Ψπ is the substochastic SR as in Definition 3.1. For a given 0 ≤ γ < 1,

γ n(s) + 1 - γ 2 1 -γ ≤ χ(s) ≤ γ n(s) + 1

Proof of Theorem 1. Let Pπ be the empirical transition matrix. We first rewrite Pπ in terms of Pπ :

Pπ (s, s ) = n(s, s ) n(s) + 1 = n(s) n(s) + 1 n(s, s ) n(s) = n(s) n(s) + 1 Pπ (s, s ) = 1 - 1 n(s) + 1 Pπ (s, s ).

The expression above can also be written in matrix form: Pπ = (I -N ) Pπ , where N ∈ R |S|×|S| denotes the diagonal matrix of augmented inverse counts. Expanding Ψπ we have:

Ψπ = γ t=0 (γ Pπ ) t = I + γ Pπ + ∞ t=2 (γ Pπ ) t = I + γ Pπ + γ 2 Pπ 2 Ψπ .

The top eigenvector of a stochastic matrix is the all-ones vector, e (Meyn & Tweedie, 2012), and it corresponds to the eigenvalue 1. Using this fact and the definition of Pπ with respect to Pπ we have:

EQUATION

We can now bound the term γ 2 Pπ 2 Ψπ e using the fact that e is also the top eigenvector of the successor representation and has eigenvalue 1 1-γ (Machado et al., 2018b):

0 ≤ γ 2 Pπ 2 Ψπ e ≤ γ 2 1 -γ e.

Plugging (5) into the definition of χ we have (notice that Ψ(s)e = ||Ψ(s)|| 1 ):

χ(s) = (1 + γ)e -(1 + γ)e + γN e -γ 2 Pπ 2 Ψπ e = γN e -γ 2 Pπ 2 Ψπ e ≤ γN e.

When we also use the other bound on the quadratic term we conclude that, for any state s,

γ n(s) + 1 - γ 2 1 -γ ≤ χ(s) ≤ γ n(s) + 1 .

In other words, the SSR, obtained after a slight change to the SR, can be used to recover state visitation counts. The intuition behind this result is that the phantom transition, represented by the +1 in the denominator of the SSR, serves as a proxy for the uncertainty about that state by underestimating the SR. This is due to the fact that s Pπ (s, s ) gets closer to 1 each time state s is visited.

This result can now be used to convert the SSR into a reward function in the tabular case. We do so by using the SSR to define an exploration bonus, r int , such that the reward being maximized by the agent becomes r(s, a) + βr int (s), where β is a scaling parameter. Since we want to incentivize agents to visit the least visited states as quickly as possible, we can trivially define r int = -|| Ψπ (s)|| 1 , where we penalize the agent by visiting the states that lead to commonly visited states. Notice that the shift (1 + γ) in χ(s) has no effect as an exploration bonus because it is the same across all states.

Table 1 : Comparison between our algorithm, termed ESSR, and R-MAX, E 3 , and MBIE. The numbers reported for R-MAX, E 3 , and MBIE are an estimate obtained from the histograms presented by Strehl & Littman (2008) . The performance of our algorithm is the average over 100 runs. A 95% confidence interval is reported between parentheses. 000, 000 3, 000, 000 3, 250, 000 3, 088, 924 (± 57, 584 We evaluated the effectiveness of the proposed exploration bonus in a standard model-based algorithm.

E 3 R-MAX MBIE ESSR RIVERSWIM 3,

In our implementation the agent updates its transition probability model and reward model through Equation 2 and its SSR estimate as in Definition 3.1 (the pseudo-code of this algorithm is available in the Appendix), which is then used for the exploration bonus r int . We used the domains RiverSwim and SixArms (Strehl & Littman, 2008) to assess the performance of this algorithm.2 These are traditional domains in the PAC-MDP literature (Kakade, 2003) and are often used to evaluate provably sampleefficient algorithms. Details about these environments are also available in the Appendix. We used the same protocol used by Strehl & Littman (2008) . Our results are available in Table 1 . It is interesting to see that our algorithm performs as well as R-MAX (Brafman & Tennenholtz, 2002 ) and E 3 (Kearns & Singh, 2002) on RiverSwim and it clearly outperforms these algorithms on SixArms.

4. COUNTING FEATURE ACTIVATIONS WITH THE SR:

In large environments, where enumerating all states is not an option, directly using the SSR as described in the previous section is not viable. Learning the SSR becomes even more challenging when the representation, φ(•), is also being learned and so is non-stationary. In this section we design an algorithm for the function approximation setting inspired by the results from the previous section.

Since explicitly estimating the transition probability function is not an option, we learn the SR directly using TD learning. In order to capture the SSR we rely on TD's tendency to underestimate values when the estimates are pessimistically initialized, just as the SSR underestimates the true successor representation; with larger underestimates for states (and similarly features) that are rarely observed. This is mainly due to the fact that when the SR is being learned with TD learning, because a reward of 1 is observed at each time step, there is no variance in the target and the predictions slowly approach the true value of the SR. When pessimistically initialized, the predictions approach the target from below. In this sense, what defines how far a prediction is from its final target is indeed how many times it has been updated in a given state. Finally, recent work (Kulkarni et al., 2016; Machado et al., 2018b) have shown successor features can be learned jointly with the feature representation itself. These ideas are combined together to create our algorithm.

The neural network we used to learn the agent's value function while also learning the feature representation and the successor representation is depicted in Figure 1 . The layers used to compute the state-action value function, q(S t , •), are structured as in DQN (Mnih et al., 2015) , but with different numbers of parameters (i..e, filter sizes, stride, and number of nodes). This was done to match Oh et al.'s (2015) architecture, which is known to succeed in the auxiliary task we define below. From here on, we will call the part of our architecture that predicts q(S t , •) DQN e . It is trained to minimize 

L TD = E (1 -τ )δ(s, a) + τ δ MC (s, a) 2 ,

δ(s, a) = R t + βr int (s; θ -) + γ max a q(s , a ; θ -) -q(s, a; θ), δ MC (s, a) = ∞ t=0 γ t r(S t , A t ) + βr int t ; θ -) -q(s, a; θ).

This loss is known as the mixed Monte-Carlo return (MMC) and it has been used in the past by the algorithms that achieved succesful exploration in deep reinforcement learning (Bellemare et al., 2016; Ostrovski et al., 2017) . The distinction between θ and θ -is standard in the field, with θ -denoting the parameters of the target network, which is updated less often for stability purposes (Mnih et al., 2015) . As before, we use r int to denote the exploration bonus obtained from the successor features of the internal representation, φ(•), which will be defined below. Moreover, to ensure all features are in the same range, we normalize the feature vector so that ||φ(•)|| 2 = 1. In Figure 1 we highlight the layer in which we normalize its output with the symbol φ . Notice that the features are always non-negative due to the use of ReLU gates.

The successor features are computed by the two bottom layers of the network, which minimize the loss

L SR = E π,p φ(S t ; θ -) + γψ(S t+1 ; θ -) -ψ(S t ; θ) 2 .

Zero is a fixed point for the SR. This is particularly concerning in settings with sparse rewards. The agent might learn to set φ(•) = 0 to achieve zero loss. We address this problem by not propagating ∇L SR to φ(•) (this is depicted in Figure 1 as an open circle stopping the gradient), and by creating an auxiliary task (Jaderberg et al., 2017) to encourage a representation to be learned before a non-zero reward is observed. As Machado et al. (2018b), we use the auxiliary task of predicting the next observation, learned through the architecture proposed by Oh et al. (2015) , which is depicted as the top layers in Figure 1 . The loss we minimize for this last part of the network is

L Recons = Ŝt+1 -S t+1 2 .

The overall loss minimized by the network is

L = w TD L TD + w SR L SR + w Recons L Recons .

The last step in describing our algorithm is to define r int (S t ; θ -), the intrinsic reward we use to encourage exploration. We choose the exploration bonus to be the inverse of the 2 -norm of the vector of successor features of the current state, that is,

r int (S t ; θ -) = 1 ||ψ(S t ; θ -)|| 2 ,

where ψ(S t ; θ -) denotes the successor features of state S t parametrized by θ -. The exploration bonus comes from the same intuition presented in the previous section, but instead of penalizing the agent with the norm of the SR we make r int (S t ; θ -) into a bonus (we observed in preliminary experiments not discussed here that DQN performs better when dealing with positive rewards). Moreover, instead of using the 1 -norm we use the 2 -norm of the SR since our features have unit length in 2 (whereas the successor probabilities in the tabular-case have unit length in 1 ).

Finally, we initialize our network the same way Oh et al. (2015) does. We use Xavier initialization (Glorot & Bengio, 2010 ) in all layers except the fully connected layers around the element-wise multiplication denoted by ⊗, which are initialized uniformly with values between -0.1 and 0.1. We followed the evaluation protocol proposed by Machado et al. (2018a) . We used MONTEZUMA'S REVENGE to tune our parameters (training set). The reported results are the average over 10 seeds after 100 million frames. We evaluated our agents in the stochastic setting (sticky actions, ς = 0.25) using a frame skip of 5 with the full action set (|A| = 18). The agent learns from raw pixels, that is, it uses the game screen as input.

Our results were obtained with the algorithm described in Section 4. We set β = 0.025 after a rough sweep over values in the game MONTEZUMA'S REVENGE. We annealed in DQN's -greedy exploration over the first million steps, starting at 1.0 and stopping at 0.1 as done by Bellemare et al. (2016) . We trained the network with RMSprop with a step-size of 0.00025, an value of 0.01, and a decay of 0.95, which are the standard parameters for training DQN (Mnih et al., 2015) . The discount factor, γ, is set to 0.99 and w TD = 1, w SR = 1000, w Recons = 0.001. The weights w TD , w SR , and w Recons were set so that the loss functions would be roughly the same scale. All other parameters are the same as those used by Mnih et al. (2015) .

Table 2 summarizes the results after 100 million frames. The performance of other algorithms is also provided for reference. Notice we are reporting learning performance for all algorithms instead of the maximum scores achieved by the algorithm. We use the superscript MMC to distinguish between the algorithms that use MMC from those that do not. When comparing our algorithm, DQN MMC e +SR, to DQN we can see how much our approach improves over the most traditional baseline. By comparing our algorithm's performance to DQN MMC +CTS (Bellemare et al., 2016) and DQN MMC +PixelCNN (Ostrovski et al., 2017) we compare our algorithm to established baselines for exploration. As highlighted in Section 4, the parameters of the network we used are different from those used in the traditional DQN network, so we also compared the performance of our algorithm to the performance of the same network our algorithm uses but without the additional modules (next state prediction and successor representation) by setting w SR = w Recons = 0 and without the intrinsic reward bonus by setting β = 0.0. The column labeled DQN MMC e contains the results for this baseline. This comparison allows us to explicitly quantify the improvement provided by the proposed exploration bonus. The learning curves of these algorithms, their performance after different amounts of experience, and additional results analyzing, for example, the impact of the introduced auxiliary task, are available in the Appendix.

We can clearly see that our algorithm achieves scores much higher than those achieved by DQN, which struggles in games that pose hard exploration problems. Moreover, by comparing DQN MMC e +SR to DQN MMC e we can see that the provided exploration bonus has a big impact in the game MONTEZUMA'S REVENGE, which is probably known as the hardest game among those we used in our evaluation. Interestingly, the change in architecture and the use of MMC leads to a big improvement in games such as GRAVITAR and VENTURE, which we cannot fully explain. However, notice that the change in architecture does not have any effect in MONTEZUMA'S REVENGE. The proposed exploration bonus seems to be essential in this game. Finally, we also compared our algorithm to DQN MMC +CTS and DQN MMC +PixelCNN. We can observe that, on average, it performs as well as these algorithms, but instead of requiring a density model it requires the SR, which is already defined for every problem since it is a component of the value function estimates, as discussed in Section 2.

6. RELATED WORK:

There are multiple algorithms in the tabular, model-based case with guarantees about their performance (e.g., Brafman & Tennenholtz, 2002; Kearns & Singh, 2002; Strehl & Littman, 2008; Osband et al., 2016) . RiverSwim and SixArms are domains traditionally used when evaluating these algorithms. In this paper we have given evidence that our algorithm performs as well as some of these algorithms with theoretical guarantees. Among these algorithms, R-MAX seems the closest approach to ours. As with R-MAX, the algorithm we presented in Section 3 augments the state-space with an imaginary state and encourages the agent to visit that state, implicitly reducing the algorithm's uncertainty in the state-space. However, R-MAX deletes the transition to this imaginary state once a state has been visited a given number of times. Ours lets the probability of visiting this imaginary state vanish with additional visitations. Moreover, notice that it is not clear how to apply these traditional algorithms such as R-MAX and E 3 to large domains where function approximation is required.

Conversely, there are not many model-free approaches with proven sample-complexity bounds (e.g., Strehl et al., 2006) , but there are multiple model-free algorithms for exploration that actually work in large domains (e.g., Stadie et al., 2015; Bellemare et al., 2016; Ostrovski et al., 2017; Plappert et al., 2018) . Among these algorithms, the use of pseudo-counts through density models is the closest to ours (Bellemare et al., 2016; Ostrovski et al., 2017) . Inspired by those papers we used the mixed Monte-Carlo return as a target in the update rule. In Section 5 we have shown that our algorithm performs generally as well as these approaches without requiring a density model. Importantly, Martin et al. (2017) had already shown that counting activations of fixed, handcrafted features in Atari 2600 games leads to good exploration behavior. Nevertheless, by using the SSR we are not only counting learned features but we are also implicitly capturing the induced transition dynamics.

Finally, the SR has already been used in the context of exploration. However, it was used to help the agent learn how to act in a higher level of abstraction in order to navigate through the state space faster (Machado et al., 2017; 2018b) . Such an approach has led to promising results in the tabular case but only anecdotal evidence about its scalability has been provided when the idea was applied to large domains such as Atari 2600 games. Importantly, the work developed by Machado et al. (2018b ), Kulkarni et al. (2016) and Oh et al. (2015) are the main motivation for the neural network architecture presented here. Oh et al. (2015) have shown how one can predict the next screen given the current observation and action (our auxiliary task), while Machado et al. (2018b) and Kulkarni et al. (2016) have proposed different architectures for learning the successor representation from raw pixels.

7. CONCLUSION:

RL algorithms tend to have high sample complexity, which often prevents them from being used in the real-world. Poor exploration strategies is one of the main reasons for this high sample-complexity. Despite all of its shortcomings, uniform random exploration is, to date, the most commonly used approach for exploration. This is mainly due to the fact that most approaches for tackling the exploration problem still rely on domain-specific knowledge (e.g., density models, handcrafted features), or on having an agent learn a perfect model of the environment. In this paper we introduced a general method for exploration in RL that implicitly counts state (or feature) visitation in order to guide the exploration process. It is compatible to representation learning and the idea can also be adapted to be applied to large domains. This result opens up multiple possibilities for future work. Based on the results presented in Section 3, for example, we conjecture that the substochastic successor representation can be actually used to generate algorithms with PAC-MDP bounds. Investigating to what extent different auxiliary tasks impact the algorithm's performance, and whether simpler tasks such as predicting feature activations or parts of the input (Jaderberg et al., 2017) are effective is also worth studying. Finally, it might be interesting to further investigate the connection between representation learning and exploration, since it is also known that better representations can lead to faster exploration (Jiang et al., 2017) .

Supplemental Material Count-Based Exploration with the Successor Representation:

This supplementary material contains details omitted from the main text due to space constraints. The list of contents is below:

• Pseudo-code of the model-based algorithm discussed in Section 3;

• Description of RiverSwim and SixArms, the tabular domains we used in our evaluation; n(s, a) ← x t(s, a, x ) r(s, a, s ) ← (t(s,a,s )-2)×r(s,a,s )+R t(s,a,s )-1

for each state x ∈ S do P (s, a, x ) ← t(s,a,x ) n(s,a)

P (s, x ) ← n(s,x ) n(s)+1

end for Ψ ← (Iγ P ) -1 r int ← -Ψe π ← POLICYITERATION( P , r + βr int ) end while

DESCRIPTION OF RIVERSWIM AND SIXARMS:

The two domains we used as testbed to evaluate the proposed model-based algorithm with the exploration bonus generated by the substochastic successor representation are shown in Figure 2 . These domains are the same used by Strehl & Littman (2008) . For SixArms, the agent starts in state 0. For RiverSwim, the agent starts in either state 1 or 2 with equal probability.

EQUATION

Figure 2 : Domains used as testbed in the tabular case. The tuples in each transition should be read as action id, probability, reward . See text for details.

EVALUATION THE IMPACT OF THE AUXILIARY TASK IN ESSR:

The algorithm we introduced in the paper, ESSR, relies on a network that estimates the state-action value function, the successor representation, and the next observation to be seen given the agent's current observation and action. While the results depicted in Table 2 allow us to clearly see the benefit of using an exploration bonus derived from the successor representation, they do not inform us about the impact of the auxiliary task in the results. The experiments in this section aim at addressing this issue. We focus on Montezumas Revenge because it is the game where the problem of exploration is maximized, with most algorithms not being able to do anything without an exploration bonus.

The first question we asked was whether the auxiliary task was necessary in our algorithm. We evaluated this by dropping the reconstruction module from the network to test whether the initial random noise generated by the successor representation is enough to drive representation learning. It is not.

When dropping the auxiliary task, the average performance of this baseline over 4 seeds in MON-TEZUMA'S REVENGE after 100 million frames was 100.0 points (σ 2 = 200.0; min: 0.0, max: 400.0). As comparison, our algorithm obtains 1778.6 points (σ 2 = 903.6, min: 400.0, max: 2500.0). These results suggest that auxiliary tasks seem to be necessary for our method to perform well.

We also evaluated whether the auxiliary task was sufficient to generate the results we observed. To do so we dropped the SR module and set β = 0.0 to evaluate whether our exploration bonus was actually improving the agent's performance or whether the auxiliary task was doing it. The exploration bonus seems to be essential in our algorithm. When dropping the exploration bonus and the successor representation module, the average performance of this baseline over 4 seeds in MONTEZUMA'S REVENGE after 100 million frames was 398.5 points (σ 2 = 230.1; min: 0.0, max: 400.0). Again, clearly, the auxiliary task is not a sufficient condition for the performance we report.

The reported results use the same parameters as those reported in the main paper. Learning curves for each individual run are depicted in Figure 3 . 3 and 4 .

Finally, Figure 4 depicts the learning curves obtained with the evaluated algorithms in each game. Lighter lines represent individual runs while the solid lines encode the average over the multiple runs. 

:

When we refer to environments with sparse rewards we do so for brevity and ease of presentation. Actually, any sequential decision making problem has dense rewards. In the RL formulation a reward signal is observed at every time step. By environments with sparse rewards we mean environments where the vast majority of transitions lead to reward signals with the same value.

Our algorithm maximizes the discounted return (γ = 0.95). We used policy iteration where the policy evaluation step is terminated when the estimates of the value function change by less than 0.01. In RiverSwim β was set to 100 and in SixArms β was set to 1000. These values were obtained after evaluating the algorithm for β ∈ {1, 10, 100, 200, 1000, 2000}. The code used to generate these results is available at: https: //github.com/ommitted/blind.

The code used to generate these results is available at: https://github.com/ommitted/blind.

Figures and Tables:

Figure 1: Neural network architecture used by our algorithm when learning to play Atari 2600 games.

Figure 3: Evaluation of the sufficiency and necessity of the auxiliary task in DQN MMC e +SR. The learning curves are smoothed with a running average computed using a window of size 100.

Figure 4: DQN MMC e +SR and DQN MMC e learning curves in the Atari 2600 games used as testbed. The curves are smoothed with a running average computed using a window of size 100.

Performance of the proposed algorithm, DQN MMC e +SR, compared to various agents on the "hard exploration" subset of Atari 2600 games. The DQN results reported are from Machado et al. (2018a) while the DQN MMC +CTS and DQN MMC +PixelCNN results were extracted from the learning curves available in Ostrovski et al.'s (2017) work. DQN MMC e denotes another baseline used in the comparison. When available, standard deviations are reported between parentheses. See text for details.

Table content: <table><tr><td/><td/><td>DQN</td><td>DQN MMC +CTS</td><td>DQN MMC +PIXELCNN</td><td colspan="2">DQN MMC e</td><td colspan="2">DQN MMC e</td><td>+SR</td></tr><tr><td>FREEWAY</td><td>32.4</td><td>(0.3)</td><td>29.2</td><td>29.4</td><td>29.5</td><td>(0.1)</td><td>29.5</td><td colspan="2">(0.1)</td></tr><tr><td>GRAVITAR</td><td>118.5</td><td>(22.0)</td><td>199.8</td><td>275.4</td><td>1078.3</td><td>(254.1)</td><td>430.3</td><td colspan="2">(109.4)</td></tr><tr><td>MONT. REV.</td><td>0.0</td><td>(0.0)</td><td>2941.9</td><td>1671.7</td><td>0.0</td><td>(0.0)</td><td>1778.6</td><td colspan="2">(903.6)</td></tr><tr><td>PRIVATE EYE</td><td>1447.4</td><td>(2,567.9)</td><td>32.8</td><td>14386.0</td><td>113.4</td><td>(42.3)</td><td>99.1</td><td colspan="2">(1.8)</td></tr><tr><td>SOLARIS</td><td>783.4</td><td>(55.3)</td><td>1147.1</td><td>2279.4</td><td>2244.6</td><td>(378.8)</td><td>2155.7</td><td colspan="2">(398.3)</td></tr><tr><td>VENTURE</td><td>4.4</td><td>(5.4)</td><td>0.0</td><td>856.2</td><td>1220.1</td><td>(51.0)</td><td>1241.8</td><td colspan="2">(236.0)</td></tr><tr><td colspan="6">5 EMPIRICAL EVALUATION OF EXPLORATION IN DEEP RL</td><td/><td/><td/></tr><tr><td colspan="10">We evaluated our algorithm on the Arcade Learning Environment (Bellemare et al., 2013). Following</td></tr><tr><td colspan="10">Bellemare et al.'s (2016) taxonomy, we evaluated our algorithm in the Atari 2600 games with sparse</td></tr><tr><td colspan="10">rewards that pose hard exploration problems. They are: FREEWAY, GRAVITAR, MONTEZUMA'S</td></tr><tr><td colspan="5">REVENGE, PRIVATE EYE, SOLARIS, and VENTURE. 3</td><td/><td/><td/><td/></tr></table>

Learning curves of DQN e and DQN MMC e +SR and their performance after different amounts of experience in the Atari 2600 games used for evaluation; • Results of additional experiments designed to evaluate the role of the auxiliary task in the results reported in the paper for ESSR.EXPLORATION THROUGH THE SUBSTOCHASTIC SUCCESSOR REPRESENTATIONIn the main paper we described our algorithm as a standard model-based algorithm where the agent updates its transition probability model and reward model through Equation 2 and its SSR estimate as in Definition 3.1. The pseudo-code with details about the implementation is presented in Algorithm 1.

Table content: <table><tr><td>Algorithm 1 Exploration through the Substochastic Successor Representation (ESSR)</td></tr><tr><td>n(s, s ) ← 0 t(s, a, s ) ← 1 r(s, a) ← 0 P (s, a) ← 1/|S| ∀s ∈ S, ∀a ∈ A ∀s, s ∈ S ∀s, s ∈ S, ∀a ∈ A ∀s ∈ S, ∀a ∈ A P (s, s ) ← 0 ∀s, s ∈ S π ← random over A while episode is not over do</td></tr><tr><td>Observe s ∈ S, take action a ∈ A selected according to π(s), and observe a reward R and a next state s ∈ S n(s, s ) ← n(s, s ) + 1 t(s, a, s ) ← t(s, a, s ) + 1 n(s) ← x ,b t(s, b, x )</td></tr></table>

Results obtained with DQN MMC e +SR after different amounts of experience.

Table content: <table><tr><td>Game</td><td>10M frames</td><td>50M frames</td><td>100M frames</td></tr><tr><td>FREEWAY</td><td>25.7 (1.5)</td><td>29.6 (0.1)</td><td>29.5 (0.1)</td></tr><tr><td>GRAVITAR</td><td>229.9 (31.3)</td><td>559.3 (75.9)</td><td>1078.3 (254.1)</td></tr><tr><td>MONT. REVENGE</td><td>0.0 (0.0)</td><td>0.0 (0.0)</td><td>0.0 (0.0)</td></tr><tr><td>PRIVATE EYE</td><td>216.7 (219.5)</td><td>109.1 (44.1)</td><td>113.4 (42.3)</td></tr><tr><td>SOLARIS</td><td colspan="3">2230.0 (322.3) 2181.5 (292.9) 2244.6 (378.8)</td></tr><tr><td>VENTURE</td><td>63.8 (31.3)</td><td colspan="2">794.1 (151.9) 1220.1 (51.0)</td></tr></table>

Results obtained with DQN MMC

Table content: <table/>

Peer review (iclr2019):
 Being familiar but not an expert in reinforcement learning, my review will focus on the overall soundness of the proposed method Summary: The authors are interested in the problem of sample efficiency in reinforcement learning, i.e. how to learn a policy achieving good performance (discounted reward) in a RL setting using as little interaction with the environment as possible. To do this the authors propose to learn a policy in a new environment where the reward has changed: an exploration bonus is added to the reward that should bias the agent towards the least frequently visited states. The algorithms proposed throughout the manuscript are extensions of a two-part algorithm of the following flavour: 1) An estimate of visitation count is done in an online fashion using a modified version of the successor representation (SR). 2) This estimates parametrizes the exploration bonus of the environment . Both learning algorithms are optimized together. This initial algorithm is fairly simple in its description and builds on well established ideas in RL. The authors then ‘evaluate the effectiveness of the proposed exploration bonus in a standard model-based algorithm’ against other baselines. They do explain how the model is learned, but not how the policy is optimized. The remainder of the manuscript applies the same idea to different settings. For large state spaces, The SR expected visits are learned using TD along with state action value functions. The counts of visitations are replaced by features that are also learned. Overall, the manuscript is rather confusing. The SSR theorem is stated (with no real intuition and the actual bounds on n(s) left for the reader to derive). It is not well motivated. Why would we want expected counts and not the discounted version? Then the remainder of the paper actually makes no use of this theorem, but only use it as a distant inspiration. Tentative connections are made such as TD underestimating SR thus leading to a result more akin to SSR, which is highly speculative. It is also irrelevant since features are learned anyway. The final proposed architecture has many additions to a simple DQN (the reconstruction + the exploration bonus + the MMC). This makes it difficult to understand what the contribution of the exploration bonus is. It does not help that results are manually extracted from histograms found in papers. Overall, although the intuition is interesting (though not so new). The overall motivation and structure of this manuscript makes think it does not match the standards of ICLR for publication