Successor-Predecessor Intrinsic Exploration
Authors: Changmin Yu
Neil Burgess
Maneesh Sahani
Samuel Gershman
Venue: NeurIPS 2023 poster (2023)
Keywords: Exploration
reinforcement learning
TL;DR: We propose a novel intrinsic exploration reward based on the combination of both prospective and retrospective information.

Abstract: Exploration is essential in reinforcement learning, particularly in environments where external rewards are sparse. Here we focus on exploration with intrinsic rewards, where the agent transiently augments the external rewards with self-generated intrinsic rewards. Although the study of intrinsic rewards has a long history, existing methods focus on composing the intrinsic reward based on measures of future prospects of states, ignoring the information contained in the retrospective structure of transition sequences. Here we argue that the agent can utilise retrospective information to generate explorative behaviour with structure-awareness, facilitating efficient exploration based on global instead of local information. We propose Successor-Predecessor Intrinsic Exploration (SPIE), an exploration algorithm based on a novel intrinsic reward combining prospective and retrospective information. We show that SPIE yields more efficient and ethologically plausible exploratory behaviour in environments with sparse rewards and bottleneck states  than competing methods. We also implement SPIE in deep reinforcement learning agents, and show that the resulting agent achieves stronger empirical performance than existing methods on sparse-reward Atari games.

Successor-Predecessor Intrinsic Exploration
Changmin Yu!
Neil Burgess' !+ Maneesh Sahani
Samuel J. Gershman 3+
Institute Cognitive Neuroscience;
Gatsby Computational Neuroscience Unit; UCL, London, United Kingdom
Department of Psychology, Harvard University, Cambridge, United States
Joint senior authors
Abstract
Exploration essential in reinforcement learning, particularly in environments where external rewards are sparse. Here we focus on exploration with intrinsic rewards, where the agent transiently augments the external rewards with self- generated intrinsic rewards. Although the study of intrinsic rewards has long his- tory, existing methods focus on composing the intrinsic reward based on measures of future prospects of states, ignoring the information contained in the retrospective structure of transition sequences. Here we argue that the agent can utilise retro- spective information to generate explorative behaviour with Structure-awareness facilitating efficient exploration based on global instead of local information. We propose Srrccessoo-Prrdeeceses rithm based on a novel intrinsic reward combining prospective and retrospective information. We show that SPIE yields more efficient and ethologically plausible exploratory behaviour in environments with sparse rewards and bottleneck states than competing methods. We also implement SPIE in deep reinforcement learning agents, and show that the resulting agent achieves stronger empirical performance than existing methods sparse-reward Atari games.
Intrinsic Exploration (SPIE), an exploration algo-
1 Introduction
The study of exploration in reinforcement learning (RL) has produced broad range of methods [ 2), ranging from simple methods such as pure randomization [ 4 to more sophisticated methods
such as targeted exploration towards states with high uncertainty (5/77] and implicit exploration with entropy maximization [8] [.. Intrinsic exploration, highly effective class of methods, intrinsic rewards based on the agent's 's current knowledge of the environment, hence informing targeted exploration towards states with high predictive uncertainty state occupancy diversity (10 However, existing approaches define the intrinsic reward based solely on prospective or empirical marginal information about future states, ignoring retrospective information (e.g., does given state always precedes the goal state, hence should be more frequently traversed?). We argue that the retrospective information contains useful signals about the connectivity structure of the environment, hence could facilitate more efficient targeted exploration. For example, consider clustered environment with bottleneck states connecting the clusters (Figure exploration based on local information (e.g., visitation counts) would discourage the agent from traversing bottleneck states, despite the key roles these states play connecting different clusters. Guiding the agents to visit such "bottleneck" states in the face of minimal local information gain is essential in driving efficient and biologically plausible exploration. Here we study the contribution of retrospective information for global exploration with intrinsic motivation.
11 6, 12
One of the most successful recent intrinsic exploration algorithms 12 uses the successor representa- tion (SR; [13 [4] to generate intrinsic rewards. The SR represents each state in terms of successor states. The row norms of the SR can be used as an intrinsic reward that generalises count-based
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

exploration [[]]. As we discuss in Section the SR contains not only prospective information, but also retrospective information about expected predecessors. This information can be utilised to construct a novel intrinsic reward which overcomes some of the problems associated with purely prospective intrinsic rewards, such as untargeted exploration, the augmented reward function is non-stationary, and asymptotic uniformity.
We provide a brief overview of background and relevant literature Section 2 and formally introduce the novel intrinsic exploration method, Siccessoo--Predecessor Intrinsic Exploration (SPIE), in Section 3 We propose two instantiations of SPIE for discrete and continuous state spaces, with comprehensive empirical examinations of properties of SPIE in discrete state space. We show that SPIE facilitates more efficient exploration. in terms of improved sample efficiency of learning and higher asymptotic return, through empirical evaluations on both discrete and continuous environments in Section 4
Background and related work
Reinforcement Learning Preliminaries. We consider the standard RL problem in Markov Decision Processes (MDP), defined by the tuple, A, Po. R, 7), where S is the state space, .A is the action space, p: 8 A (SS) is the state transition distribution (where (SS) is the probability simplex over S), Po E (SS) is the initial state distribution, R S x A + I is the reward function, and learn the optimal policy that maximises value (expected cumulative discounted reward): x" (a|s) )) = argmax, g" (s, a), V(s, a) E S x A, where x S A(A) the policy, and q" (s. a) is the state-action value function:
7 (0, is the discount factor. The goal for an RL agent
(s, a) Ep EE== R( a-) (s0 8, ag
pp [R(s, a) + (5 a'))
(1)
where PT (s E. ( (()ss))(P (s'(s, a) is the marginal state transition distribution given मf The second equality is the recursive form of the action value function known as the Bellman equation 15]. which underlies temporal difference learning [I:
1dd (8t, a+) - q" (St, ax) + ad,, 8, = rt + " (8++1, (c+1) - 1td (8t, az),
where (st, 0z) the current estimate of the action values (with respect to σ), òG the (one- step) temporal difference (TD) error. We will study the effect of different intrinsic rewards on the performance of online TD learning (SARSA) in discrete state MDPs.
The successor representation. The SR is defined as the expected cumulative discounted future state occupancy under the p
M[s, s' Ep- 7 s') s] Ep- [1(so. s') + (M(1 s')(so = s].
(3)
Given the recursive formulation, it is possible to learn the SR matrix online with TD learning. Given the transition tuple, (Se, at; Ft, 8t+1 1 1,+1, the update
M Mise, s' + M Msr,. s'1 + ao.,
SM (st, 7 M(s+1,,8)
M[s
(4)
Note that these equations are analogous to TD learning for value function estimation, except that in this case the function being learned is vector-valued (one-hot) representation of future states.
First-occupancy representation. The SR captures the expected cumulative discounted state occu- pancy over all future steps. However, in many real-world and simulated tasks, it may be preferable to reach the goal state as quickly as possible instead of as frequently as possible. In this spirit, Moskovitz al. [66] introduced the First-occupancy Representation (FR). Formally, the FR matrix in a discrete MDP is defined by
F Fis, =Ep
Σ 1 (s+ s' {su:r 1) =
= EEp [1(,,, 8') + 7(1 - (st, s')) F(88111, 8 811ss, =
Note that unless otherwise stated, we assume deterministic MDP, i.e., P(s') a) a delta function. FFrr notational simplicity, we keep the policy dependence implicit. Similar notational choice holds for all quantities discussed in the rest of the paper (F and N).

---

where {so:r} = {su. $1......77 $1....,88-11- The recursive formulation implies that there is an efficient TD learning rule for online learning of the FR matrix. Given the transition tuple (st, at Pei St41 (t+1). the update rule is
Fise, s'1 + Fist, + ast, of 1st, s') (1 (s,,, 5) s'),
(6)
Intrinsic exploration in RL. Here we focus exploration with intrinsic motivation, where the agent augments the external rewards with self-constructed intrinsic rewards based on its current knowledge of the environment.
(s, a) = (s, as,a) + (s,
(7)
where ( a) denotes the extrinsic environmental reward, (s, denotes the (possibly non- stationary) intrinsic reward, and /3 is a multiplicative scaling factor controlling the relative balance of (s (s,a) and (s, a). The intrinsic reward often operates by motivating the agent move into under-explored parts of the state space in the absence of extrinsic reinforcement. Many types of
intrinsic rewards have been proposed, including functions of state visitation counts [17-19] predictive uncertainty of value estimation [5), and predictive error of forward models [o 6 20 In a closely related work, Zhang et [2 proposes NovelD, which constructs the episode-spectie
non- non-negative intrinsic reward based on the difference between the novelty measures of temporally adjacent states along a trajectory. However in contrast to SPIE (discussed later), the key difference is that NovelD does not explicitly utilise the retrospective information for exploration and the associated intrinsic reward is episode-dependent.
3
Successor-Predeeesson Intrinsic Exploration
Existing intrinsic exploration methods construct intrinsic rewards based on either the predictive information a temporally forward fashion (e-g., predictive error), or the empirical marginal distribution (e.g., count-based exploration). Here we argue that the retrospective information inherent in experienced trajectories, though having been largely overlooked in the literature, could also be utilised as a useful exploratory signal. Specifically, consider the environment in Figure La (Cluster- simple), where the discrete grid world is separated into two clusters connected by a "bottleneck" state. Whenever the starting and reward locations are in different clusters, the bottleneck state, s., always precedes the goal state, regardless of the trajectory taken. Hence, the frequent predecessor state (e.g., sx), to the goal state should be traversed despite the fact that immediate information gain by traversing the state is minimal. In the absence of extrinsic reward, if only utilising learned prospective information based on past experience (e.g., the norm of the online-learned SR [12),, the intrinsic motivation for exploration is merely local hence would discourage transitions into bottleneck states. However, the retrospective information different sub-regions of the state space, hence incorporating the connectivity information of the state space into guiding exploration, allowing the agent to escape local exploration and navigate towards bottleneck states to reach distant regions.
be utilised identify the state transitions that connect
We develop Predecessor Intrinsic Exploration (SPIE) algorithm utilising intrinsic rewards based on both prospective and retrospective information from past trajectories. Below we provide instantiations of SPIE based on the SR for discrete and continuous state spaces.
SPIE discrete state space. We define the SR-Relative (SR-R) intrinsic reward, which is defined as the SR of the future state from the current state minus the sum of the SRs of the future state from all states. Formally, given a transition tuple, (s, a, r, s',, a'), we define the SR-R intrinsic reward as:
TSR-R(S, a) = M[s, s' MM: (1sss") s'Ill = Σ M
(8)
SES,
The above equation holds in deterministic MDPs (i.e., when s' is function of (s, a)). We note that the j-th column of the SR matrix represents the expected discounted occupancy to state j. starting from every state, hence constituting temporally backward measure of the accessibility of state j [22]. Therefore, F (s, a) consists of both a prospective measure (M[s, [s, s')) and retrospective measure ( (JMM) J., s'] (']l I), and exploring with I'sR an instantiation of SPIE discrete MDPs. Intuitively, FSR-R( (8) can be interpreted as penalising transitions leading into states s' that are frequently reached from many states other than 8, hence providing an intrinsic motivation for guiding the agent towards states that are harder to reach in general, e.g, boundary states and bottleneck states. We thoroughly
3

---

investigate the individual contribution of prospective and retrospective information through ablation studies Appendix [B.4] and we observe that prospective information alone does not yield optimal exploration performance, whereas utilising only the retrospective information does not degrade exploration efficiency, indicating the importance of global topological information contained in the retrospective information for intrinsic exploration.
In closely related work, Machado et al. [12] showed that (s)(() = 1/ M/M :IIla can be used as an intrinsic reward that facilitates exploration in sparse reward settings. They additionally showed that the row norm of the online- SR matrix implicitly approximates the state visitation counts, so the resulting behaviour resembles count-based exploration. However, a key issue associated with U'R is that the asymptotic exploratory behaviour is uniformly random across all states, i.e.,
[M[s:]] :Il++ -> 1/(1 - 7). Vs E S. We note that exploration involves learning of both the environ- mental transition structure pd and the reward structure R. Hence, were the SR matrix to be known priori (hence 7n could be implicitly derived), no intrinsic motivation would be introduced at any state and the resulting agent regresses back to random exploration, omitting further efficient exploration for learning R. Since TSR-R contains the sum of columns of the SR matrix, the asymptotic uniformity in 'SR no longer holds, yielding non-trivial intrinsic exploration even when the SR matrix is known and fixed a priori, allowing continual exploration for learning the reward structure despite sparse extrinsic reinforcement.
Analysis of "SR-R with pure exploration in grid-worlds. We examine exploration based on (s in discrete worldorlds with different topologies (Fig. Ta We first consider pure exploration in the absence of extrinsic reward, and evaluate the exploratory behaviours of 4 RL agents with different intrinsic rewards, in terms of their state coverage. The agents we consider are: vanilla SARSA D: SARSA with vsR (SARSA-SR; [2)); SARSA with (s) = ||F|s,:]l (SARSA-FR: [6):: ); and SARSA with TSR-R (SARSA-SRR) the pseudocode for SARSA-SRR can be found in Appendix). We consider 4 different grid-world environments with different configurations (Figure Ta namely, 10 x 10 open-field grid
10 10 grid with two rooms (Cluster-simple); 10 x 10 grid with 4 rooms (Cluster-hard) and 20 x 20 open-field grid (OF-large).
Exploration efficiency is quantified as the number of timesteps taken to cover 50, 90% and 99% of the state space. The value estimates for all states are initialised to be 0. Due to the absence of extrinsic reward, the vanilla SARSA agent is equivalent to random walk policy, which acts as a natural baseline. We observe from Figure Tb that SARSA-SRR yields the fastest coverage of the state space amongst all considered agents. The SARSA-FR agent yields similar state coverage efficiency as SARSA. SARSA-SR performs poorly in all 4 wooddssrdds, failing to achieve 50% state coverage within 8000 timesteps in all environments other than the simplest one (OF-small) Moreover, we observe that SARSA-SPE performed consistently across the 4 considered grid configurations. whereas all other agents experienced significant degradation in exploration efficiency as the size and complexity of the environments increase.
We note that in addition to improved exploration efficiency, SARSA-SRR exhibits "cycllnn" behaviour in pure exploration in the 20 x 20 two-cluster environment (Figure (e)), spending the majority of its time exploring in one cluster and periodically traverses the "bottleneck" states to explore the opposing clusters upon sufficient coverage of the current cluster. Such "cycling" strategy exhibits short-term memory of recent states and consistent long-term planned exploration towards regions more distant in history. This is potentially advantageous for environments with non-stationary reward structures ((23), such real-world foraging, which require continual cxploration for identifying new rewards. We verify the capability of SARSA-SRE for dealing with non- non-stationary reward structure in Section 4 (Figure B)
The complexity of analysing the properties of SARSA-SRR is two-fold: the online learning of the SR matrix and the online update of the Q-values. By assuming the SR matrix is known and fixed throughout training we observe from Figure Ic that SARSA-SRR consistently outperforms all competing methods, Similar to what we observed when the SR (FR) matrix is learned online. Additionally, we observe that the exploration efficiency for all three intrinsic exploration agents drops when using the intrinsic reward constructed with the fixed SR (FR), but SARSA-SRR yields minimal decrease comparing to the significant degradation with SARSA-SR and SARSA-FR. Hence, we have empirically confirmed that the improved exploration efficiency does not stem solely from the online learning of the SR matrix, but is a property of FSR Another long-standing issue with many existing
We assume the policy the fixed SR matrix is dependent on is the random walk policy unless otherwise stated.

---

OF-small
Cluster-simple
Cluster-hard
OF-large
(a)
130
0F-mma
Chigendimple
Custre hand
OF-laree
150
1000
1930
1139
1988
(b)
Or-omal
Chumanhers
2000 2000 1000
180 2039 2009 500 700
2300 3008
500 700
2000
2000 500
6538
2030
24p
(c)
Figure 1: Evaluation of exploration efficiency in grid worlds. (a) Grid worlds with varying size and complexity. 'S' and "G' in OF-small and Cluster-hard represents the start and goal states in the goal-oriented reinforcement learning task; colored G and G2 in OF-small and Cluster-hard represent the changed goal locations (see the non-stationary reward experiment in Section 4 Cluster-simple denote the bottleneck state. (b-c) Accumulated number of states visited against exploration timesteps, for all considered agents in all grid-worlds in with (a) online-learned SR matrix (b) and fixed SR matrix (c). All reported results are averaged over random seeds (shaded area denotes mean + standard error). Hyperparameters can be found in Appendix.
intrinsic exploration methods is the non-stationary nature of the associated intrinsic bonus. By fixing the SR (FR) matrix, the associated PSR-R stationary whilst still yielding high exploration efficiency, hence validating the utility of SPIE.
SPIE in continuous state space with deep RL. In order to generalise JSr.r r to continuous state space, we replace the SR with successor features (SF: 24)
[xb" (8L+1, (+++1))) 8: = s, a, 26 (s. a) = De x f lt = 8, a = a| (($++1) E
where (ss, a) a feature representation such that r(s, a) = Φ(s, a) w. with weight parameter w. The recursive formulation for SF admits gradient-based learning of by minimising the following squared TD loss.
SF =E (0(s,, + 1b(5441, ac+1) - (f a.))
(10)
where the transition tuple (st, at, S1+1, 11-1) can be taken from either online samples (SARSA-like) or sampled from offline trajectories (Q-learning-like We previously noted that the column of the SR matrix provides a marginal retrospective accessibility of states, facilitating stronger exploration. However, there is no SF-analogue of the column of the SR matrix. We therefore construct retrospective exploration objective with the Predecessor Representation (PR), which was proposed to measure how often a given state is preceded by any other state given expected cumulative discounted preceding occupancy [25] The formal definition for the PR matrix under discrete MDP,
5

---

N E ||S|X|S is defined as following.
T
N[s, 5'] Eep
7'1 (s, 81,,,nn-111 8n Σ
s Epp [1( sn) (N
Sn-1l]
(11)
where the expectation is based on Pr (st = s|s141 8²) p (s(e)) the retrospective transition
s(e")
model, and z(s) lim Ep- (s,, s)], denotes the stationary distribution given policy x.
Utilising the recursive formulation for the PR matrix, we can again derive a TD-learning rule. Namely, given the transition tuple, (st, de. Tb, S1+1, a++1), we have the following update rule.
Ñ 55 s141] = N(3, s + ad, 6 1 (s:+1, + N, sr] - Ni5, stt1]-
(12)
The SR and PR have reciprocal relationship (proof in appendix):
Nziag(z) diag(z)M,
(13)
where diag(z) E ||S||| denotes the diagonal matrix whose diagonal elements corresponds to the discrete stationary distribution of the MDP under the current policy.
Similar to how SF generalises SR, we propose the "Predecessor Feature" (PF) that generalises PR.
(st)) c (8) = E Σ> o 7 p =] ((+++1) >IB ( 8, 0r aa (14)
Similarly the SF, the recursive definition of the PF again allows simple expression of the TD error for gradient-based learning of the PF.
%
PF E ((b(s++1) + ~E(s)) {(s(+1)))
(15)
We utilise the norms of SF and PF to replace the row sums in discrete settings for tractable approxi- mation to F'R-R R in continuous state spaces. We use the same feature vector, Ø, for computing the SF and PF. In order ensure the SF and PF are of similar scales across the state space, we normalise d(s) such that [|ø())l22 the SR and the column sum of the SR in discrete MDP we find that setting the intrinsic reward as the difference between the reciprocal of the norms of the SF and the PF yields better empirical performance, We hence define continuous Successor-Predeeessoo intrinsic reward as follows.
for all Contrary to how we define rSR-R as the difference between
TSE-FF
|| (b((s,,)))l)
(16)
Details of deep RL implementation of TSE-PF. We instantiate TSF-PF based on
Deep Q Network (DQN; (66)), with auxil- iary predictive reconstruction task (Crecon
MIP
S,,.
E (8411 - [sc] where 8.+1 is the pre- dicted next state), and separate heads for com- puting the valuues. the SF, and the PF, respec- tively (Figure 2) We call this model DQN-SF- PF. Note that, following Machado et al. [12], the intermediate feature representation á is trained given only the predictive reconstruction and value learning supervisions, and not updated given the TD error in the learning of the SF or the PF (the filled black circle in indiia-t operation). We adopt the same set of hyperparameters and architecture for the DQN as reported in Oh al. (27]. To make the comparison consistent, we utilise the
10, 4.
Cone
ag
MLP
Figure 2: Graphical illustration of the neural net- work architecture of DQN-SF-PP for Atari games. Note that the state feature vector L2-normalised, ((s) I2a the convolutional encoder.
ing the stop_gradin
ă(x) where Φ(s) is the raw output of
Note refer discrete/continuous MDP an MDP with discrete/continuous state and action space.

---

Table Evaluations SARSA-SRE and related baseline agents on RiverSwim and SixArms (averaged over 100 seeds, numbers in the parentheses represents standard errors).
SARSA
SARSA-SA SR
SARSA-FR
SARSA-SRE
SARSA-SR-PP
RiverSwim
25,075
1,197,075
1,547,243
547, 156
857,, 324
(1,224)
(36,999)
(34,050)
(479,655)
(419,922)
SixArms
376,655
1,025,750
119,149
2, 199, 291
1, 845, 229
(8,449)
(49,095)
(42,942)
(1,024,726)
(1,032,050)
mixed Monte-Carlo return loss as following.
28
defined
bg E (11 T)) 7
(17)
where (s a)
f (s()), + Brsper o;; ((s,
t=
where ÔTD denotes the standard TD error for q-values (Eq. 2), is the scaling factor controlling the contribution of the TD error and the Monte Carlo error, and 0 and 0 denote the parameters for the online and target DQN-SF-PF, respectively. Hence the overall loss objective for training DQN-SF-PF is as following.
LDQN SF WgLy + WsFd + uppd PF Wreeoon Crecon
(18)
where WigSsE/Priecoo denotes the scaling factors for the respective loss terms. The complete set of hyperparameters for DQN-SF-PE can be found in the Appendix.
Experiments
Classical hard exploration tasks. We evaluate performance of the discrete SPIE agent (and other considered agents in Section SARSA, SARSA-SR, SARSA-FR) on two classical hard exploration tasks commonly studied in the PAC-MDP literature, RiverSwin and SixArms (2 (appendix Figure In both tasks, environment transition dynamics induce bias towards states with low rewards, leaving high rewards in states that are harder to reach. Evaluation of the agents is based on the cumulative reward collected within 5000 training steps.
We observe from Table that SARSA-SRE significantly outperforms all other considered agents. Moreover, in order to further justify the utility of RSR-R in driving exploration, we run ablation studies by evaluating the performance of variants of SARSA-SRE (Appendix B.44). Ablation studies reveal the importance of combining both prospective and retrospective information for exploration, as well as the benefits of dynamic balancing exploring uncertain states and bottleneck states.
In order to validate the replacement of column norm of the SR with column norm of the PR in the construction of FSR-R, given the reciprocal relationship (Eq. 13). we empirically evaluate the performance the SARSA agent with the alternative intrinsic reward, T'R-PR (s, a) Mís, s [| ss'Ill. SARSA-SR-PR yields comparable performance as SARSA-SR, on both RiverSwim and SixArms (Table D. empirically justifying the instantiation of SPIE with the PR for capturing the retrospective information.
Goal-oriented/ sparse-reward tasks. We next evaluate the agents on grid world tasks with single terminal goal state (Figure Iaj OF-small and Cluster-hard). All non-terminal transitions yield rewards of -1 and transitions into the goal state generates reward 0. Such goal-directed or sparse-reward tasks require efficient exploration. We examine both open-field and clustered grid- worlds. In OF- small and Cluster-hard tasks, SARSA-SRE outperforms both vanilla SARSA and SARSA-SR in terms of sample efficiency (Figure B) In addition, SARSA-SRR yields more stable training and performance more robust across different random seeds. Note that the navigation performance of SARSA-SR during training is highly unstable, which might attribute to its equivalence to count-based exploration given that visitation count is only a local measure for exploration. Somewhat surprisingly, the improvement for SARSA-SRE is more significant in open- field grid world (OF-small) rather than
7

---

OF-small (stationary)
Gusterhard (stationar))
-10
-10
-20
-20
-30
-30
cpsoodic neRum
-50
100
100
20
30
40
50
0
10
20
40
*pisndes
opisndes
(a)
(b)
Cluster-hard (non-statinoary)
Clusten-hard (non-statinoary)
-20
-20
optrodic return
-60
-60
Sarse
Sarza
-80
Sansa
Sarse-5h SR
Sarse-SR
-100
-100
(c)
Figure 3: Goal-oriented navigation in grid worlds Evaluations of SARSA, SARSA-SR and SARSA-SRR on Om-sllll (a) and Cluster-hard (b) grid worlds (Figure Tap with stationary reward structure, and OF-small (c) and Cluster-hard (d) with non-stationary reward structures. The red dashed horizontal line represents the shorted path distance. The black dashed vertical lines represent the time point at which the goal change occurs.
the clustered grid world (Cluster-hard), contrast to the pure exploration experiments (Figure lbp. Nevertheless, the improvement is strong and consistent.
In many real-world tasks, the environment is inherently dynamic, requiring continual exploration for adapting the optimal policy with respect to the non-stationary task structure. One such example random foraging, where foods are depleted upon consumption, and rewards appear in new locations. As argued in Section 3 SARSA-SRR yields "cycling" exploratory behaviour (Figure 66), hence could facilitate continual exploration that is potentially suitable for such non-stationary envi- ronments. To empirically justify the hypothesis, we consider the Non-Markovian Reward Decision Process (NMRDP: (23)), where the reward changes dynamically given the visited state sequence. We instantiate the NMRDPs in the grid worlds, OF-small and Cluster-hard, where there are three reward states (G, G1 G2; Figure Tap that are sequentially activated (and deactivated) every 30 episodes. As shown in Figure 3e and 3d we observe that SARSA-SRE consistently outperforms SARSA and SARSA-SR. reaching the new goal states in increasingly shorter timescales. This supports our idea that SPIE provides a more ethologically plausible exploration strategy for dealing with non-stationarity. However, we note that main focus of the current paper is on improved exploration within single task, instead of over stream of inter-related tasks. Here we provide preliminary evidence of potential applicability of SPIE in such continual exploration setting, and we leave more rigorous investigation this direction for future work.
Linear function approximation for continuous state spaces. We next evaluate SPIE with function approximation. As first step, we consider the linear features before moving onto the deep RL setting. We consider the MountainCar task (Figure 4al 30)). with sparse reward structure, where we set the reward to 0 for all transitions into non-terminal states (the terminal state is indicated by the flag on top the right hill). We utilise Q-learning with linear function approximation, where we define the linear features to be the I 22-dimensional random Fourier features (RFF (31]: Figure 4b). The SF and the PF are defined given the RFF, and are learned via standard TD-learning (Eq. TO T5). The performance (over the first 1000 training episodes) of the resulting linear- Q agents with l'sF and

---

Fst
E5r
(a)
(b)
(c)
Figure 4: Evaluation of SPIE with linear features in MountainCar. (a) Graphical demonstration of MountainCar environment; (b); Example random Fourier features; (c) Evaluations of Q-learning with linear function approximation with intrinsic rewards rsF and TSF-FF MountainCar. Reported results are averaged over 10 random seeds.
Table 2: Evaluations of SPIE with deep RL implementation hard-exploration Atari games (averaged over 10 random seeds, numbers in the parentheses are standard errors).
DQN
DQN
RND
DQN SR
DQN -SF-PF
Freeway
32.4 (0.3)
29.5 (0.1)
28.2 (0.2)
29.4
27.5 (0.2)
Gravitar
118.5 (22.0)
1078.3 (254.1)
714.1 (105.9)
457.4 (120.3)
1223.0 (408.9) 9)
Mont, Rev.
0.0 (0.0)
(0.0)
528 (314.0)
1395.4 (11218)
1530.0 (1072.1)
Private Eye
1447.4 (2,56.99)
113.4 (42.3)
61.3 (53.7)
104.4 (50.4)
488.2 (390.9)
Solaris
2132.6 (394.8)
1395.2 (401.7)
1890.1 (163.1)
2455.8 (262.0)
Venture
(5.4)
1220.1 (51.0)
953.7 (167.3)
1348.5 (56.5)
1274.0 (133.2)
TSFPF is shown Figure 4c The agent with TSF-F outperforms the opposing agent significantly, empirically justifying the utility of SPIE in the linear function approximation regime.
Deep RL instantiation of SPTE in Atari games. We empirically evaluate DQN 6 Atari games with sparse reward structures [32]: Freeway, Gravitar, Montezuma's 's Revenge, Private Eye, Solaris, and Venture. We follow the evaluation protocol as stated in Machado et al. [33. where report the averaged evaluation scores over 10 random seeds given 10t training steps. The agent takes (stacked) pixel observations as inputs. Across all games, the 3 values are and the discounting factor & 0.995. We adopt the epsilon-annealing scheme as in (28) which linearly decreases from 1.0 to 0.1 over the first 10th frames. We train the network with RMSprop. with standard hyperparameters, learning rate 0.00025, discounting factors for value learning and online learning of the SF and the PF are set 0.99. The scaling factors in Eq, 18 are set such that the different losses are on roughly similar scales: w, 1, WSF 1500, Upp 1500, Wreeom 0.001. More implementation details can be found in Appendix.
0.07
0.001 and decay equals 0.95 26) The
We compare DQN-SF-P with vanilla DQN trained with standard TD error, vanilla DQN trained with the MMC loss (Lg). Random Network Distillation (RND; 20)). DQN-SR trained with the MMC loss 12
(Table All agents are trained with the predictive reconstruction auxiliary task. By comparing with main baseline, DQN-SR, we observe that DQN-SF-PF significantly outperforms DQN-SR on Four games (Gravitar, Montezuma's Revenge, Private Eye and Solaris), whilst yielding similar performance on the remaining two games (Freeway and Venture). Moreover, DQN-SF-PF outperforms RND, state-of-the-ar Deep RL algorithm for exploration, on all 6 games. The empirical difference only reflected in the asymptotic performance, but also in the sample efficiency of learning. Specifically, for Montezuma'ss 's Revenge, one of the hardest exploration games in the Atari suite, our agent achieves near asymptotic performance (defined as the score given 10 training steps) with only 8 x 10" training frames, whereas the performance of DQN-SR saturates at ~ 2.4 x 10" training frames (with a lower score). We emphasise that the main aim of our empirical evaluations to validate the utility of SPIE exploration objective as simple modification to DQN. In principle, SPIE can integrated with any -fate-of-the-art RI. agent, and different instantiations of SPIE could be implemented to deal with the task at hand. We leave such investigation for future work.

---

Conclusion
The development of more efficient exploration algorithms is essential for practical implementation of RL agents in real-world environment where sample efficiency and optimality are vital success. Here, we propose a general intrinsically motivated exploration framework, SPIE, where we construct intrinsic rewards by combining both prospective and retrospective information contained in past trajectories. The retrospective component provides information about the connectivity structure of the environment, facilitating more efficient targeted exploration between sub-regions of state space given structure awareness (c.g., robust identification of the bottleneck states; Figure Tap. SPIE yields more sample efficient exploration discrete MDPs under complete absence of external reinforce- ment. Moreover, side benefit we observe empirically is that SPIE exhibits ethologically plausible exploratory behaviour during exploration in grid worlds (i.e., cycling between different clusters of states). In continuous state space, we developed novel generalization of the predecessor representa- tion, the predecessor features, for capturing retrospective information in continuous spaces. Empirical evaluations on both discrete and continuous MDPs demonstrate that SPIE yields improvements over existing intrinsic exploration methods, in terms of sample efficiency of learning and asymptotic performance, and for adapting non-stationary reward structures.
We instantiate SPIE using the SR and the PR, but we note that SPIE is a general framework that can be implemented with other formulations (e.g., predictive error in a temporally backward direction [34 35 and with more advanced neural architectures (including those currently unthought of). Although here we have examined the empirical properties of SPIE, the theoretical underpinnings for SPIE and the bottleneck seeking exploratory behavior bears further investigation. Specifically, more work needs to be done to probe the theoretical property of using SF and PF in continuous settings. Our definition of 'SRR overlaps with the successor contingency [25] [ which has long been recognised for learning causal relationship between predictors and reward [37]. An interesting venue for future work is to investigate the implications of SPIE for causally guided exploration in RL. Another interesting direction for future work is to investigate the implications of SPIE in human exploration, where we could utilise SPIE to investigate how human balance local (c.g., visitation counts) versus global (e.g., environment structure) information for exploration in sequential decision tasks 38 39].
36.
Acknowledgement
We thank Franziska Brändle, James Heald, and Ted Moskovitz for useful discussions, and anonymous reviewers for valuable comments. This work is funded by the UKRI, DeepMind, the Gatsby Charitable Foundation, the Simons Foundation, the Wellcome Trust, and the Harvard Brain Initiative and by the Center for Brains, Minds and Machines (CBMM).
References
[1] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[2] Susan Amin, Maziar Gomrokchi, Harsh Satija, Herke van Hoof, and Doina Precup. A survey of exploration methods in reinforcement learning. arXiv preprint arXiv:2109.00157, 2021.
[3] Gerald Tesauro et al. Temporal difference learning and td-gammon. Communications of the ACM, 38(3):58-68, 1995.
[4] Will Dabney, Georg Ostrovski, and André Barreto. Temporally-extended (Vepsiton)-greed, exploration. arXiv preprint arXiv:2006.01782, 2020.
[5] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016.
[6] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity driven exploration by self-supervised prediction. International conference on machine learning, pages 2778- 2787. PMLR, 2017.
10

---

[7] Michael Laskin, Hao Liu, Xue Bin Peng, Denis Yarats, Aravind Rajeswaran, and Pieter Abbeel. Cic: Contrastive intrinsic control for unsupervised skill discovery. arXiv preprint arXiv:2202.00161, 2022.
[8] Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-regullaiized 2017.
markov decision processes. arXiv preprint
[9] Tuomas Haarnoja, Aurick Zhou, Picter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[10] Jürgen Schmidhuber. Curious conference neural networks, pages 1458-1463, 1991.
control systems. In Proc. international joint
[11] Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv: 1.07507, 2016.
[12] Marlos Machado, Marc G Bellemare, and Michael Bowling. Count-basee exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5125-5133, 2020.
[13] Peter Dayan. Improving generalization for temporal difference learning: The successor repre- sentation. Neural computation, ((4)) 544)66336244 1993.
[14] Samuel J Gershman. The successor representation: its computational logic and neural substrates. Journal of Neuroscience, 38:7193-7200, 2018.
[15] Richard Bellman. Dynamic programming. Science, 153(3731):34-35 1966.
[16] Ted Moskovitz, Spencer R Wilson, and Maneesh Sahani. A first-occupancy representation for reinforcement learning, arXiv preprint arXiv:2109. 13863, 2021.
[17] Peter Dayan and Terrence Sejnowski. Exploration bonuses and dual control. Machine Learning, 25:5-22 1996.
[18) Richard S Sutton. Integrated modeling and control based on reinforcement learning and dynamic programming. Advances in neural information processing systems, 3, 1990.
[19] Justin Fu, John Co-Reyes, and Sergey Levine, Ex2: Exploration with exemplar models for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
[20] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint 1810.
2018.
[21] Tianjun Zhang, Huazhe Xu, Xiaolong Wang. Yi Wu, Kurt Keutzer, Joseph E Gonzalez, and Yuandong Tian. Noveld: A simple yet effective exploration criterion. Advances in Neural Information Processing Systems, 34:25217-25230, 2021.
[22] Duncan Bailey and Marcelo Mattar. Predecessor features. arXiv preprint arXiv:2206.00303,
2022.
[23] Sylvie Thiébaux, Charles Gretton, John Slaney, David Price, and Froduald Kabanza. Decision- theoretic planning with non-markovian rewards. Journal of Artificial Intelligence Research, 25: 17-74. 2006.
[24] André Barreto, Will Dabney, Rémi Munos, Jonathan Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30, 2017.
[25] Vijay Mohan K Namboodiri and Garret Stuber. The learning of prospective and retrospective cognitive maps within neural circuits. Neuron, 109(22):352-33775 2021.
[26] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1022v.331..5002, 2013.

---

[27] Junhyuk Oh, Xiaoxiao Guo, Honglak Lee, Richard L Lewis, and Satinder Singh. Action- conditional video prediction using deep networks in atari games. Advances in neural information processing systems, 28, 2015.
[28] Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
[29] Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309-1331 2008.
[30] Andrew William Moore. Efficient memory-based learning for robot control. Technical report, University of Cambridge, 1990.
[31] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
[32] Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279 2013.
[33] Marlos C Machado, Marc G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018.
[34] Changmin Yu, Dong Li, Jianye Hao. Jun Wang, and Neil Burgess. Learning state representations via retracing in reinforcement learning. arXiv preprint arXiv:2111.12600) 2021.
[35] Tao Yu, Cuiling Lan, Wenjun Zeng, Mingxiao Feng, Zhizheng Zhang, and Zhibo Chen. Playvir- tual: Augmenting cycle-consistent virtual trajectories for reinforcement learning. Advances in Neural Information Processing Systems, 34:5276-5289, 2021.
[36] Charles R Gallistel, Andrew R Craig, and Timothy A Shahan. Temporal contingency. Be- havioural processes, 101:89-96, 2014.
[37] Herbert M Jenkins and William C Ward. Judgment of contingency between responses and outcomes. Psychological monographs: General and applied, 79(1):1, 1965.
[38] Daniel Acuna and Paul R Schrater. Structure learning in human sequential decision-making. Advances in neural information processing systems, 21, 2008.
[39] Franziska Brändle, Lena J Stocks, Joshua Tenenbaum, Samuel J Gershman, and Eric Schulz. Intrinsically motivated exploration as empowerment. 2022.
[40] Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, (10e))2213231,, 2002.
12

---

A More Details on Predecessor Representation
Here we provide proofs of the reciprocal relationship between the SR and the PR.
Proposition A.1. Ndiag(z) diag(z)M, where diag(z) is the diagonal matrix with the diag- onal elements as the vector z, and z is the vector of stationary distribution of pn (i.e. z(i] lim; Ep Stc = il.
11.. have the following analytical Proof. Given the formal definition of the SR and the PR (Eq. expressions.
M (1 >; N -1-
(19)
where TDT is the temporally reversed transition distribution. Assume matrix formulation p and PO., and P in x||, we have the following.
Pij P(st i|st+1 = [((+++ = j|st i))((8 =
Pizz (20)
P(8++1 =j
2j
Pdiag(z) = diag(z)) P
Substituting the reciprocal relationship between and P into the definition the PR, we have the following.
(1 > diag (d)aag))
Ndiag(z) (I 7 diag (Ziagg))P
diag(z)
(diag( z - (1 (ddaa(())diag(z))
(21)
((1 --P)diag(z)
diag(z) ((1 pP)
diag(z)M
B Further results on tabular hard exploration tasks.
B.1 Graphical illustration of tabular hard-exploration tasks.
The demos of RiverSwim and SixArms shown in Figure 5 both tasks, the environmental transition dynamics impose asymmetry, biasing the agent towards low-rewarding states that easier to reach, with greater rewards available in hard-to-reach states.
ALLABOOK
O- SAMEE
(L122500
JOLVE 10000
AEALLAUI
J- SARE-IR
S6
ALBLIGAD (ELTACOO)
TANEE
ILLIGOOS
TLL DULOS
(a) RiverSwim
(b) Arms
Figure 5: Discrete MDPs, Transition probabilities are denoted by (action, probability, reward). In RiverSwim (a), the agent starts in state or 2. In SixArms (b), the agent starts in state 0.
13

---

Table 3: Evaluations on RiverSwim and SixArms with intrinsic rewards based on fixed SR/FR
(averaged over 100 seeds, numbers in the parentheses represents standard errors).
SARSA-SR
SARSA-FR SARSA-SRR
RiverSwim
327,402
278,096
3,096,913
(787,118)
(666,752)
(230,059)
SixArms
969,781
1,143,037
2,059,424
(2,895,306)
(1,939,021)
(3,292,936)
B.2 Pseudocode for SARSA-SRR.
We provide the pseudocode for SARSA LARSA-SRRIIA in Algorithm | SARSA-FR utilise the similar algorithm, but only replacing the intrinsic bonus.
We note that SARSA, SARSA-SR and
Algorithm Pseudocode for SARSA-SRE
Require: a, 7). y. 7SR. 8, e
= enc.reset():
M = 0 E IR S||Ss
D Initialise the SR matrix zero matrix
Q [
while not done do
~ (((, 1);
if 0 < then
> e-greedy policy
a ~ U(A):
else
== argmax Q[s,a];
end if
s'.r, done = etv.stepla);
M[s,:] M[s.:] + (1(s) + 7sR done) Mis M(s;:]); TTD-eearning of the SR
r = r r 3-M s1 |
b Constructing intrinsic reward
o' ~ U(00 1);
0' < then
a' U(A);
else
argmax Q|s a[s..a]:
end if
[s Q[s + (r done) Q(s Q[s,a];;
= s
end while
B.3 Evaluations given the fixed SR.
Conforming to our analysis of TSR with fixed SR (Section we additionally evaluate SARSA- SR/FR/SRR with the corresponding intrinsic rewards constructed based fixed SR/FR matrix on RiverSwim and SixArms (Table Similar to what we found in the grid worlds (Figure [c], both SARSA-SR and SARSA-FR perform worse than their online-SR counterparts (note one exception being SARSA-FR on SixArms). However, in contrast the decrease in exploration efficiency of SARSA-SRR in grid worlds, we found that fixing the SR actually improves the performance of SARSA-SRU Hence, accord with our analysis in Section the cause for the improved empirical performance of FSR-R does not lie solely in the online learning process of SR, but might stems from the inherent "bottleneck-seee seeckig property TSR-R-
B.4 Ablation studies of SPIE in discrete tasks
We perform ablation studies on SARSA-SRR for further demonstration the utility the SPIE objec- tive of combining both the prospective and retrospective information. We firstly show that prospective
14

---

Table Ablation studies of SARSA- on RiverSwim and SixArms.
SARSA-SRR
SARSA-SRR(a) SARSA-SRRIS
SARSA (RR(()
RiverSwim 2, 547, 156
127,703
2, 629, 947
95,691
(479,655)
(530,564)
(930,170)
(181,216)
SixArms 2, 1999, 291
893,530
1, 9,902, 553
562,346
(1,024,726)
(2,601,324)
(2,211,960)
(1,748,455)
information alone cannot yield strong exploration, whereas utilising solely the retrospective infor- mation maintains the strong explorative performance. We consider two variants of SARSA-SRR, SARSA-SRR(a) and SARSA-SRR(D), with the respective intrinsic rewards as following.
(o (s, a, 5') [s, s'],
(sR-Roj(S, as), - |:
(22)
From Table we observe that utilising the prospective information alone for exploration yields suboptimal performance, hence empirically justifying the utility of the SPIE framework. However, do observe that utilising the retrospective information alone yields near- or supra-optimal performance. Together, the results indicate that the global topological information contained in the retrospective information is essential for intrinsic exploration purposes.
We argue that the dynamic balancing between exploring states with high uncertainty and bottleneck states is a key factor driving the empirical success of SPIE. In order to test this hypothesis, we devise variant of the RSR-R.
(23) Intuitively, Rsa Rie) provides intrinsic motivation for taking transitions that lead to states that less reachable from s, which only yields exploration towards states of high uncertainty, but does not provide any motivation towards bottleneck states. Indeed, CARSA-SRR(C also yields suboptimal performance, providing empirical evidence supporting the benefits of SPIE in driving the agents towards bottleneck states.
Ric [| [s, =IIla M[ss'),
observe from Table 4 that
C Further results on exploration in grid worlds
C.1 Transient dynamics of exploration.
We look more closely at the transient dynamics of the considered agents during pure exploration in Cluster-simple-large (where Cluster-simple-lae denotes the 20 x 20 grid world with two clusters). We observe that in the absence of external reinforcement, SARSA-SR, regardless of based on intrinsic rewards given either online-learned or fixed SR matrix, exhibits minimal exploration (Figure 6a 6b). This is largely due to its local exploration behaviour. For SARSA-FR, we observe sigmfiicant difference between using online-trained and fixed FR matrix, where exploration with intrinsic rewards based on fixed FR completed disrupts exploration, only exploring a small proportion of the environment. In contrast, we observe that SARSA-SRR consistently fully explores both clusters (repeatedly) under both conditions. Additionally, by closely examining the transient dynamics during the exploration phase, observe the "cycling" behaviour
C.2 Effeet of optimistic initialisation.
We note that across all considered SARSA agents, the Q values were initialised to be 0 for all state action pairs. Given that all SR entries are non-negative, we know that FSR-R only admits negative rewards, hence the zero-initialisation yields optimistic initialisation, which encourages the agent to explore 440 29]. To disentangle the effect of SPIE from optimistic initialisation, we perform the ablation study on pure exploration with augmented SARSA- SR and SARSA-FR agents with optimistic mitialisation. Specifically, we note that the maximum value the SR entries can take - and additionally since the FR entries, by definition, are always less than or equal to the corresponding
$ seee the attached videos in supplementary materials for the full exploration dynamics for the considered agents
15

---

X
(b)
Figure 6: Pure exploration given fixed SR / FR measures. Temporal evoluation of state coverage heatmaps over 6000 training steps of (a) SRASA-SR; (c) SARSA-FR; (e) SARSA-SRA agents with intrinsic rewards based on fixed SR/FR measures in OF-small; and (b). (d), (f) for the counterparts with online-trained SR/FR measures the 20 x Cluster-simple grid world. From left right: 200, 400, 600, 800, 1000, 1500, 2000, 3000, 4000, 5000, 6000 steps.
16

---

Custa had
26
SHRANGTE
Figure 7: Ablation study optimistic initialisation exploration efficiency. We evaluate SARSA, SARSA-SRR, and optimistically augmented SARSA-SR and SARSA-FR on the considered grid worlds (Figure Ta
SR entries, we initialise the Q values for all state-action pairs for both SARSA-SR and SARSA- FR to be --x- We evaluate the exploration efficiency for the optimistically augmented agents on the grid worlds (Figure 7) and observe that despite the optimistic initialisation improves the performance of both SARSA-SR and SARSA-FR relative to their corresponding naive counterparts, the performance differences in terms of exploration efficiency between the augmented agents and SARSA-SPE are significant, hence justifying the utility of the SPIE framework independent of the optimistic initialisation.
D Further results on deep RL implementation of SPIE in Atari games
D.1 Ablation study on the effect of predictive reconstruction auxiliary task
In our implementation of DQN-SF-PF, by following relevant literature 27 12], we include an additional sub-module in the neural architecture for predicting action-dependent future observation, which trained via minimising the predictive reconstruction error. The purpose of including this sub-module is purely for learning better latent representations underlying the visual observation. We validate the utility of such predictive reconstruction auxiliary supervision by performing ablation study. We implemented an alternative version of DQN-SF- SF-F, removing the visual reconstruction sub-module, and test on Montezuma's Revenge. The resulting model achieves 551.5 points (averaged over 5 random seeds, s.e. equals 618.4). We observe that there is significant decrease from standard DQN-SF-PF (Table indicating the importance stronger representation learning given the predictive reconstruction auxiliary task. Moreover, given the reported performance of 398.5 points (s.e., equals 230.1) of DQN-SF in the absence of predictive reconstruction auxiliary task from Machado al. [12] we observe that the SPIE objective still yields improved performance over exploration with SF alone, justifying the utility of SPIE irrespective of the specific neural architecture choose.
E Experiment Details
Here we provide further details of the experiments presented in the main paper.
Tabular tasks. We hyperparameter sweeps for all considered agents (SARSA, SARSA-SR. SARSA-FR, SARSA-SRR) on the following hyperparameters: (0.005, 0.05, 0.1, 0.25, 0.5) for learn- ing rate of TD learning for the values (a): (0.005, 0.05, 0.1, 0.25, 0.5) } for learning rate of TD learning for the SR/FR matrices (n): {0.5, 0.8, 0.9, 0.95, 0.99} for the discounting factor defining the SR/FR formulation (?SR/RR:: {1, 10, 50, 100, 1000, 10000} for the multiplicative scaling factor controlling the scale of the intrinsic rewards (8); {0.01, 0.05, 0.1} } for the degree of randomness in e-greedy exploration (e). The complete sets of optimal hyperparameters for the reported performance [ (and for the corresponding agents with intrinsic rewards based on fixed SR/FR matrix; Table 3 in shown in Table
of the considered agents in Table
Exploration in grid worlds. For all presented results in the grid worlds, we use the hyperparameters (0.1, 0.1, 0.95, 0.95, 1.0, 0.1) for (a, 7), 7, 7,R/FR,
Mountain Car experiment. We use the 128-dimensional random Fourier features, defined over the two-dimensional state space doocatiooxspeedd as the state representation. We use the hyperparameters
17

---

Table Hyperparameters for the considered agents in the tabular expl-explooation tasks (the values in parentheses are the corresponding hyperparameter values for the learning of the PR).
agent
7
/SRFFR
B
RiverSwim
SARSA
0.005
0.95
0.01
SARSA-SR
0.25
0.1
0.95
0.95
10
0.1
SARSA-FR
0.25
0.01
0.95
0.95
50
0.1
SARSA-SRK
0.1
0.25
0.95
0.95
10
0.01
SARSA-SR-PR
0.25
0.25(0.1)
0.95
0.95(0.99)
0.01
SARSA-SR (fixed)
0.01
0.95
0.95
10
0.05
SARSA-FR (fixed)
0.1
0.95
0.95
10
0.1
SARSA-SRR (fixed)
0.25
0.95
0.95
10
0.01
SixArms
SARSA
0.5
0.95
0.01
SARSA-SR
0.1
0.01
0.95
0.99
100
0.01
SARSA-FR
0.1
0.01
0.95
0.99
100
0.01
SARSA-SRR
0.01
0.01
0.95
0.99
10000
0.01
SARSA-SR-PR
0.05
0.25(0.25)
0.95
0.95(0.99)
10
0.01
SARSA-SR (fixed)
0.5
0.95
0.95
1
0.01
SARSA-FR (fixed)
0.5
0.95
0.95
1
0.01
SARSA-SRU (fixed)
0.5
0.95
0.95
10
0.01
(0.1, 0.2, 0.2, 0.99.......... 0.95, 0.95, 1000, 0.3) for (a,, 77, MPR 7 7SR, "PRR, 3,c), where 7/R and yPu the learning rate and discounting factor values for the PR, respectively.
Atari experiments. The neural architecture of the deep RL implementation shown in Figure 2 here we provide the specific hyperparameters of the architecture. The Conv block convolutional network with the configuration (4. 84, 84, 0,2) (6.2)-RReA4 Re-L- (64, 40, 40, 2) -0-RReLU-- (64, 6, 6, 2) ReLU - (64, 10, 10, 0, 0) - (1024))), where the tuple represents 2-dimensional convolutional layer with the architecture (num filters, kernel_ _idthh kernel height, padding size, stride), and FC(1024) represents fully connected layer with 1024 hidden units. We take the output of the Conv block the 1024-dimensional state representation given the observation, which is then subsequently used for computing the SF and the PF. The action input is transformed into a high-dimensional embedding through linear transformation, FC(0048). The MLP for the predictive reconstruction block is FC(2048) ReLU, for the Q-value estimation block is FC((A)), for the SF head block is FC(2048) ReLU FC(11)4), for the PF head block is FC(2048) The Deconv block FC(2048) FC(1024) (64, 2) (64, 6, 2, (1, 6, 6, 0, 2) Flatten, where the tuple represents 2-dimensional deconvolutional layer with parameters ( num filters, kernel width, kernel height, padding size, stride
ReLU FC(0024). Reshape ((64, 10, 10))
ReLU FC(64400)
18


Reviews:
[{"review_id": "Y8qQSzL9Oe", "reviewer": "Reviewer_WHHE", "summary": "The paper proposes to use both successor feature of s and predecessor feature of s' as intrinsic reward to improve RL exploration. Specifically, in the tabular case, the proposed intrinsic reward encourages the agent to visit states that are infrequently visited from other states, using successor representation which measures visitation frequency of s' from s and from other states. Then the method replace the visitation frequency from all states to s' with the predecessor representation of s'. Finally, to extend to continuous state spaces, the method approximate successor and predecessor representations with successor and predecessor features.", "questions": "Beyond the questions above:\n* What do the agent trajectories look like? Do they follow the motivation of visiting the bottleneck state?\n* Eq 8 reminds me of the motivation in the \"diversity is all you need\" paper where different trajectories should visit different parts of the state space. Are the two papers related? If so, how? Adding this discussion would be helpful.\n* Is the reconstruction necessary? An ablation study would be helpful.\n* What are the confidence intervals like in Fig 4 (c)?\n* Why is RND missing in Table 2 Freeway row? Any explanation for the worse performance of the proposed method on the private eye?", "limitations": "The only limitation is the lack of motivation of replacing successor/predecessor representation with their corresponding features for continuous state space.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "1. Intrinsic reward is an important way to improve RL exploration and thus sample efficiency, and the proposed method is well motivated (to visit bottleneck states more frequently), to the best of my knowledge, is novel.\n2. The experiments are well designed, ranging from tabular to gridworld to atari to show the effectiveness of each variation of the method: (1) using successor representation along, (2) replacing row sum of successor representation with predecessor representation, and (3) replacing representations with features.\n3. The background of successor representations is written clearly, preparing readers well for the proposed method.", "weaknesses": "1. The method section is well structured, but it can be improved in the following places:\n\n* It's clear that successor representation means the visitation frequency from s to s', and using Eq 8 follows the proposed motivation of encouraging visitation to s' that are rare from states other than s. Then, for continuous state space, the authors replace successor representation with successor feature. But why does the successor feature could represent the visitation frequency? After the replacement, does the intrinsic reward still follow the same motivation? I feel this replacement is not well explained/motivated.\n* For the successor/predecessor feature, different feature columns may have different value ranges (scales). How to account for that to avoid certain feature columns dominating the column sum?\n* Any possible explanation for the form of the reciprocal of norms in Eq. 16? What are other forms that you tried but underperform?\n* Why is reconstruction needed? It's unclear how much the reconstruction contributes to representation learning and exploration.\n* When the authors mention the \"row/column sum\" of some symbol, the shape of the referred symbol (including which is row and which is column) is usually not introduced and thus confusing, including but not limited to L192.\n* Figure 1: why does SARSA-SR perform so badly?\n* (minor) unintroduced symbols and typos: L165 \"diffusion\" (you can probably remove \"diffusion\"), Eq 14 $\\mu$, L181 N's shape missing \"|\", Fig 2 the lines are mixed together and thus a bit hard to read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their instructive comments. Please find below our replies to the raised concerns/questions.\n\n- The generalisation to continuous state space means that we can no longer enumerate all states for the computation and learning of the SR. Hence we adopt a natural extension of the SR to continuous setting, the successor features. The SF also exhibits the similar predictive encoding as the SR in discrete settings, hence could also represent the prospective transition information in continuous setting (similarly the retrospective information for the predecessor features). Empirically, we find the generalisation to SF work well with our models and previous models (e.g., Machado et al., 2020) using either linear or non-linear function approximation, hence justifying our choice. \n\n- In our implementation of the SF-PF-DQN, both the SF and the PF are based on the intermediate features ($\\phi_{t}$ in Figure 2), which are L2-normalised for avoiding the scaling issue. This is done with F.normalize(phi, p=2, dim=-1) (see line 105 in atari/models/sr_pr_dqn.py in the provided codes).\n\n- The initial proposal was to use the difference of norms of the SF and PF as is done for the SR in discrete settings. However, we find it hard to set the scaling factor for the SPIE intrinsic reward in this case. We hence adopt the reciprocal form presented in Machado et al., 2018 (last equation on page 5), which we find to yield robust performance on a range of $\\beta_{spie}$ values (0.03-0.06). We note that the fundamental principle of SPIE is the combination of prospective and retrospective information for exploration, admitting different instantiations (including those shown in equation 8 and 16). \n\n- In our implementation of DQN-SF-PF, by following relevant literature [oh et al., 2015, Machado et al., 2020], we include an additional sub-module in the neural architecture for predicting action-dependent future observation, which is trained via minimising the predictive reconstruction error. The purpose of including this sub-module is purely for learning better latent representations underlying the visual observation. We validate the utility of such predictive reconstruction auxiliary supervision by performing ablation study with an alternative version of DQN-SF-PF, removing the visual reconstruction sub-module. Testing on Montezuma's Revenge, the resulting model achieves $551.5$ points (averaged over $5$ random seeds $\\sigma^2=618.4$). We observe that there is a significant decrease from standard DQN-SF-PF, indicating the importance of stronger representation learning given the predictive reconstruction auxiliary task. Moreover, given the reported performance of $398.5$ points ($\\sigma^2=230.1$) of DQN-SF in the absence of predictive reconstruction auxiliary task from Machado et al., 2020, we observe that the SPIE objective still yields improved performance over exploration with SF alone, justifying the utility of SPIE irrespective of the specific neural architecture we choose.\n\n- We will include the shape of the referred row/column sum and corresponding features, and keep the notations consistent in the updated manuscript. Thanks for pointing it out.\n\n- As mentioned in the analysis in Section 3, one possible explanation for the poor performance of SARSA-SR is its equivalence to count-based exploration (Machado et al., 2018). Count-based exploration algorithms perform poorly in larger state space such as grid worlds (in contrast to 6 and 7 states for RiverSwim and SixArms) such that the agent preferentially explores local region for an extended time before moving to novel sub-region, hence leading to poor exploration efficiency. \n\n- We thank the reviewer for pointing out the typos, which we have fixed in the updated manuscript.\n\n- We have sample video containing a sampled trajectory of SARSA-SRR in the grid world. As is also discussed in the main paper, the SARSA-SRR agent tends to balance the motivations of visiting bottleneck states and exploring uncertain state, hence the typical behavior is the agent spend some time exploring the current cluster, and upon sufficient coverage it would move directly to the bottleneck state for exploring other clusters. In the two-cluster environment, we indeed observe such behavior where the agent spend the majority of its time exploring one of the clusters and transition into the bottleneck states upon reaching sufficient coverage. \n\n- The relationship between SPIE and DIAYD lies in their connections to the empowerment objective, which facilitates diverse exploration trajectories. We thank the reviewer for pointing out the connection, which we have now included associated discussions in the related work section.\n\n- Yes the reconstruction is necessary empirically, see the fourth point above.\n\n- We have now included the new Figure 4c with standard error in the rebuttal letter.\n\n- We have now included the Freeway evaluation (28.2 points with $\\sigma^2=0.2$, see Table 1 in the rebuttal letter). One possible reasoning for the relatively poor performance on Private Eye across all agents apart from vanilla DQN is that the background of the observation is frequently changing (unlike other games such as Venture and Montezuma's revenge), hence imposing large intrinsic exploration signals much more often comparing to other tasks, such that the agent spends the majority of its time exploring instead of focusing on maximising the reward. This is coherent with the observation that DQN without any intrinsic exploration behaves best on Private Eye whereas other agents with intrinsic exploration behaves poorly. \n\nWe wish to thank the reviewer again for their thoughtful comments, and we hope the above replies address all concerns/questions raised by the reviewer. If so, we hope the reviewer could adjust their score accordingly. If there is any remaining confusion/concern, please let us know as soon as possible and we are happy to engage in further discussion. \n"}, {"review_id": "Mv3EMD4Kyz", "reviewer": "Reviewer_pKLV", "summary": "This paper proposes Successor-Predecessor Intrinsic Exploration (SPIE), an exploration framework that uses the successor representation (SR) and predecessor representation (PR) to formulate intrinsic motivation for exploration. Amongst the variations, two specific design of intrinsic rewards are highlighted: SR-R and SF-PF. While the first directly use the successor and predecessor representations to calculate the intrinsic reward for tabular case, the latter utilizes successor and predecessor features for a smooth expansion to continuous state spaces. The experiments show that the highlighted reward designs display a promising  results.", "questions": "Some questions. \n- For SR-R, since $\\mathbf{M}[s,s'] \\le \\mathbf{M}[:,s']$, the intrinsic reward is likely to be negative, which can possibly discourage the agent to proceed to a longer episodic length when terminal state exists and can be discovered. Could this be a problem to applying SR-R to such tasks?\n- I did not fully follow how the learned $\\phi$ preserves the property $r = \\phi \\cdot \\mathbf{w}$. Also, what are the conditions for $\\phi$ and $\\mu$ to be shared? (which I suspect is the case based on Figure 2, since $\\mu$ is not clearly defined or described in the paper)\n- The score for RND seems far too off from what I would expect based on previous works, even regarding the number of training frames. Could the authors provide more details on the RND implementation? Also the score is missing for Freeway, whereas in the text, it reports 4 tasks (line 297).\n\nMinor remarks.\n- The sentence before Eqn. 10 and the equation itself have period at the end, which should be commas. Similar punctuation errors can be found in other equations.\n- The caption for Table could be more specific.\n- Tables would look more nicer if they are resized, fitted to the textwidth.\n- several notations are not clearly explained, e.g., $\\hat q^\\pi$, $\\mu$", "limitations": "The limitations are stated in the conclusion. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a unique and novel approach to exploration problem in RL. Furthermore, leveraging the successor representation displays a broad future directions of application as the successor representation are taken to be helpful in the view of generalizability in RL. ", "weaknesses": "The presentation needs some finishing touches and variables and logics are left unexplained in places. Also the experiments seem to be done in relatively small scales, whereas the the algorithm is not restricted small scales. For example, training curves of more Atari task, trained for longer period (since hard-explorations can often take more experiences), may show more clear pattern of learning. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their instructive comments. Please find below our replies to the raised concerns/questions.\n\n- Thanks for pointing out the missing of explanations of variables and logics in the current manuscript. In responding to other reviewers' comments, we have modified our manuscript for clearer demonstration and explanation. For instance, we now make clear that the main focus of the paper is on proposing stronger intrinsic exploration algorithm rather than continual exploration in non-stationary environments. We now give a more elaborate explanation on why SARSA-SR behaves poorly in pure exploration. Moreover, we provide more details on the description of the model and associated implementations. We hope these modifications have made the paper clearer and more rigorous. If there is any additional confusion remaining, could the reviewer provide specific pointers to places where we have such omission?\n\n- Through the experimental studies, instead of only showing that it yields higher performance on different tasks, we aim to maximally demonstrate the exploratory behaviours of SPIE, hence justifying our extensive evaluations on (relatively) small-scale tasks such as grid worlds. We show the final performance (at 100M training steps) instead of the training curves since we do not have the resources to run all selected baseline algorithms on all presented Atari games, hence we reporting the asymptotic performance from existing literature (e.g., from Machado et al. 2018), which prohibits us from showing the full training curve. However, we do wish to note it is common in the literature to only report the final performance instead of the full training curve in practice, therefore we do not think it would negatively affect faithful validation of the model.\n\n- As the reviewer correctly points out, the $r_{\\text{SR-R}}$ intrinsic reward is negative. However, in tasks with terminal states (usually denoting reward state), we believe it is usually preferable to reach the target state as quickly as possible. SARSA-SRR agent yields stronger exploration efficiency for faster detection of the goal states, which could then facilitate further exploration and learning for finding shorted paths towards the goal states. \n\n- The successor feature generalises SR to continuous state space, and requires a notion of state representation for constructing the similar cumulative future occupancy measure. Hence the SF is defined as the expected discounted cumulative sum of future state representations. The motivation of leveraging a state representation that could represent the reward vector as a linear transformation of the representation is based on the motivation that the SF wish to yield the similar decomposition of value function into the dot product between the SR/SF and reward vector. $\\mu$ and $\\phi$ are the same vector as we wish to construct the SF and the PF with the same state representation. We apologise for the missing notation. We now define define the PF using the same feature vector as the SF, $\\vec\\xi^{\\pi}(s) = \\vec\\mu(s_{t+1}) + \\gamma\\mathbb{E}\\left[\\vec\\xi^{\\pi}(s_{t})|s_{t+1}=s, a_{t}=a\\right]$ in the updated manuscript.\n\n- The evaluation of RND agent on Freeway was missing since we did not have the computational resources to finish all evaluations. We have provided the RND performance on Freeway in the updated manuscript (28.2 points, $\\sigma^2 = 0.2$). The main reason behind the difference in our evaluation of RND and existing evaluations reported in the literature is the reward scheme is set differently in our implementation comparing to the original implementation from Burda et al., 2018. Specifically, we report the canonical cumulative episodic reward, whereas the original implemented bin the rewards to {+1, 0, -1} by its sign, which results in larger episodic return (see, e.g., https://github.com/openai/random-network-distillation/blob/f75c0f1efa473d5109d487062fd8ed49ddce6634/atari_wrappers.py#L220). We have now included the evaluation results of DQN-SF-PF (and other baselines) on two more hard-exploration atari games, Gravitar and Solaris. Empirical results indicate that DQN-SF-PF outperforms DQN-SR on both tasks.\n\n- We thank the reviewer for pointing out the punctuation errors, which we have corrected in the updated manuscript and will be included in the camera-ready revision upon acceptance.\n\n- We have expanded the description in the table captions for clarity. We have also reduced the width of the table such that it now fits to the textwidth. These modifications will be included in the camera-ready revision upon acceptance. Thanks for the suggestions.\n\n- We thank the reviewer for pointing out the unclear notation in the paper, which we have now included the associated explanations in the updated manuscript.\n\nWe wish to thank the reviewer again for their thoughtful comments, and we hope the above replies address all concerns/questions raised by the reviewer. If so, we hope the reviewer could adjust their score accordingly. If there is any remaining confusion/concern, please let us know as soon as possible and we are happy to engage in further discussion. \n"}, {"review_id": "Q8PGBhu2uc", "reviewer": "Reviewer_dj2L", "summary": "This paper introduces a new intrinsic reward (termed SPIE) for encouraging exploration in reinforcement learning. Unlike existing methods that mainly focus on prospective information, SPIE also incorporates retrospective information into the intrinsic reward. SPIE combines successor representation (SR) and predecessor representation (PR). The effectiveness of SPIE is validated in experiments on discrete grid worlds, continuous MountainCar, and 4 Atari games.", "questions": "Apart from the points raised above, I have some questions and comments:\n- Figure (a): Can the authors comment on why SARSA-SR performs much worse than random walk (SARSA)? Maybe it is limited to such tabular cases. Usually, random exploration is not a strong baseline in high-dimensional domains.\n- Line 40: What are \"some of the problems\"?\n- Line 195: How does it perform if we define $r_\\textrm{SR-R}$ in a similar way as in discrete MDPs?\n- What if we define the intrinsic reward as $r(s,a,s')=\\lVert\\hat{M}[s,:]\\rVert_1 - \\hat{M}[s,s']$? The intuition is to encourage transitions that are less reachable from $s$. How does it perform compared to SPIE?\n- Table 1 is wider than the text width.\n- Figure 4(c): Please include the standard deviations of the results in the figure.", "limitations": "The limitations of the proposed method are barely discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The idea of combining both prospective and retrospective information in exploration is interesting.\n- This paper is in general clear and well-written.", "weaknesses": " - Beyond the performance gain, there lack in-depth discussions on the disadvantages of solely using prospective information and the benefits of adding retrospective information.\n - Line 105: The authors mention that retrospective information incorporates the connectivity about the state space. I am not sure if it can be considered an advantage that is specific to retrospective information. In my understanding, the prospective SR is also able to capture the connectivity between two states.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their instructive comments. Please find below our replies to the raised concerns/questions.\n\n- The retrospective information can be leveraged for identifying essential predictors for reward states, hence exploration using the retrospective information allows the agent to traverse the predictor (in our case, the bottleneck states) frequently regardless of the immediate information gain. In addition to demonstrate empirical performance on benchmarks, we also conducted extensive experimental studies in grid worlds to demonstrate the utility of SPIE framework. Specifically, we show that SPIE leads to improved exploration efficiency and state coverage in the complete absence of extrinsic reward. We additionally show that SPIE yields cycling exploratory behaviour, i.e., traversing the bottleneck state to reach other clusters upon reaching sufficient coverage of the current cluster, enabling the agent to adapt well to non-stationary environment. We show that the utility of the discrete SPIE intrinsic reward, $r_{\\text{SR-R}}$ does not arises solely from its negative nature (hence optimistic initialisation). We also show that the advantage of SPIE lies in its formulation of combining the prospective and retrospective information, by demonstrating that $r_{\\text{SR-R}}$ with fixed SR also yields strong exploration efficiency. If there is any additional analysis the reviewer thinks would be useful for demonstrating the utilities of SPIE, we are happy to conduct such analysis and engage in further discussion.\n\n- The reviewer is correct that the prospective information (i.e., the SR) also contains the connectivity information. However, the retrospective information provides a marginal accessibility of the target state (s') from all other states, hence providing a better sense of the local connectivity pattern of the target state that could be useful for, e.g., distinguishing states in the centre of the environment and bottleneck states.\n\n- One possible explanation for the poor performance of SARSA-SR is its equivalence to count-based exploration (Machado et al., 2018). Count-based exploration algorithms perform poorly in larger state space with sparse reward settings, such as grid worlds. Such agents preferentially explore local region for an extended time before moving to novel sub-region, hence leading to poor exploration efficiency.\n\n- Existing intrinsic exploration methods exhibit a number of problems. For instance, a notable problem is undirected exploration, whereas SPIE provides explicit intrinsic motivation towards bottleneck states. Additionally, as the agent continues exploring the state space, the intrinsic bonus decreases to 0 asymptotically, hence does not provide any intrinsic bonus for facilitating sustained exploration, which would lead to slow response to non-stationarity. Another issue associated with existing intrinsic exploration methods is the non-stationary reward structure imposed by the additive intrinsic bonus. Here we show that SPIE yields a sensible exploration bonus even with fixed SR (PR), hence resolving the non-stationary intrinsic reward issue whilst maintaining efficient exploration. \n\n- We find that defining the SPIE objective in continuous state space as the difference in norms of SF and PF leads to difficult hyperparameter tuning and we do not have the computational resources to run comprehensive grid. The reciprocal form yields robust performance on a range of $\\beta$ values (0.03-0.06). We hence choose to instantiate DQN-SF-PF with equation 16. \n\n- Using $r(s, a, s') = ||\\hat{M}[s, \"]||_{1} - \\hat{M}[s, s']$ yields intrinsic exploration based solely on state uncertainty, but does not provide any targeted exploration motivation. However, a key principle underlying SPIE is dynamically balancing exploring under uncertainty and the implicit motivation towards bottleneck states. We implemented the agent with the suggested intrinsic bonus on both Riverswim and SixArms. The empirical performance of the resulting agent on the two tasks are $95,961\\pm181,216$ and $562,346\\pm 1,749,455$, respectively, which is significantly lower than the performance of SARSA-SRR on the two tasks ($2,547,156\\pm 479,655$ and $2,199,291\\pm1,024,726$, respectively).  \n\n- We thank the reviewer for pointing out the formatting issue, we have now reduced the width of Table 1.\n\n- We thank the reviewer for pointing out the missing of standard error in Figure 4c, which we now include in the rebuttal letter. Given some further hyperparameter tuning, the resulting agent with $r_{\\text{SF-PF}}$ now yields a significantly higher average completion probability than the agent with $r_{\\text{SF}}$ comparing to Figure 4c in the current main paper, further justifying the utility of SPIE.\n\n- The limitations of SPIE mainly lie in its theoretical underpinning. In the paper we empirical verified a number of benefits brought by SPIE. However, it is hard to analytically derive the asymptotic properties of SPIE. For instance, is there a fixed point to the non-Markovian reward decision process problem in the complete absence of extrinsic reward? Further work is required in this direction. Moreover, our definition of SPIE objective in the discrete setting coincides with the successor contingency definition [Gallistel et al., 2014], and the SC quantity is shown to contain useful information about the essential predictor of reward states. Our analysis in the current paper does not arise from a causal perspective, which is a promising venue for future investigation. \n\nWe wish to thank the reviewer again for their thoughtful comments, and we hope the above replies address all concerns/questions raised by the reviewer. If so, we hope the reviewer could adjust their score accordingly. If there is any remaining confusion/concern, please let us know as soon as possible and we are happy to engage in further discussion. \n"}, {"review_id": "dV79cQzEGU", "reviewer": "Reviewer_7ZrB", "summary": "This paper is about exploration in Reinforcement Learning. Many existing works do not leverage retrospective information when computing intrinsic rewards. To this end, the paper introduces a method called SPIE where the intrinsic reward is calculated by combining successor and predecessor representations to account for prospective and retrospective information, respectively. There are different variants for discrete state space and continuous state space respectively. For discrete state space, the paper presents results on grid worlds of varying difficulty to test the efficacy of agents at covering the state space and adaptation when rewarding states change (in a continual setting). For continuous state space, comparisons on hard-exploration tasks in the Atari benchmark are presented where gains in performance are observed on a few tasks.", "questions": "1. There are methods focusing on using the retrospective structure of the transition sequences- NovelD [1]. Furthermore some recent methods have also relied on episodic novelty in addition to global intrinsic reward to improve exploration- NGU [2], E3B [3]. How does the proposed method compare with them?\n\n2. Between lines 29-33, it is mentioned that the existing method (as they don't use retrospective information) may fail to visit bottleneck states. It is not clear why this will happen. Can this be shown experimentally on the grid world example? Also, it is possible that the intrinsic reward for visiting the bottleneck state can be small. Still, the agent will receive high rewards on going to the other side of the cluster, resulting in a higher Q-value and encouraging the agent to visit those states. \n\n3. Lines 130-134 talk about continual exploration but focus on single-task settings. The NovelD [1] paper talks about the Asymptotic Inconsistency (page 4) of the exploration bonus so the agent can learn to exploit and converge to an optimal policy for the given task. For singleton tasks why having continual exploration is important? Furthermore, the paper does not discuss methods focusing on continual exploration or compare with them.\n\n4. Lines 153-159 show that the proposed agent has cyclic behavior and mentions that this is advantageous for a non-stationary reward structure. However, the experiments are mostly designed for singleton tasks. Several methods have studied adaptation in continual tasks [4] or procedurally generated tasks [5,6,7]. How does the proposed method compare with them?\n\n\n5. Was the proposed method also evaluated on how much coverage the agent can achieve in a single episode of finite length to validate if the method is suitable for non-stationary tasks?\n\n\n6. Line 126 mentions that SR-based exploration is not ideal as the asymptotic behavior is uniform across states due to the norm becoming a fixed constant. Won’t the reward based on SF+PF face the same issues as the norm will be constant upon convergence? This would not help with continual exploration as discussed for the discrete case and may lead to different behaviors than the reward defined for the discrete state space scenario.\n\n7. Experiments on Atari: There is no reasoning provided on why the method does better on Montezuma’s Revenge and Private Eye, and does poorly on Freeway and Venture. [5] also compared on Gravitar and Solaris, it would be interesting to see comparisons on these 2 environments too. Furthermore, more recent works should be included in the baselines like SPR [8].\n\n8. Minor typo: Line 127: were -> where\n\n### References:\n[1] Zhang, Tianjun, et al. \"Noveld: A simple yet effective exploration criterion.\" Advances in Neural Information Processing Systems 34 (2021): 25217-25230.\\\n[2] Badia, Adrià Puigdomènech, et al. \"Never give up: Learning directed exploration strategies.\" arXiv preprint arXiv:2002.06038 (2020).\n[3] Henaff, Mikael, et al. \"Exploration via Elliptical Episodic Bonuses.\" arXiv preprint arXiv:2210.05805 (2022).\\\n[4] Lehnert, Lucas, Stefanie Tellex, and Michael L. Littman. \"Advantages and limitations of using successor features for transfer in reinforcement learning.\" arXiv preprint arXiv:1708.00102 (2017).\\\n[5] Zha, Daochen, et al. \"Rank the episodes: A simple approach for exploration in procedurally-generated environments.\" arXiv preprint arXiv:2101.08152 (2021).\\\n[6] Raileanu, Roberta, and Tim Rocktäschel. \"Ride: Rewarding impact-driven exploration for procedurally-generated environments.\" arXiv preprint arXiv:2002.12292 (2020).\\\n[7] Wang, Kaixin, et al. \"Revisiting intrinsic reward for exploration in procedurally generated environments.\" The Eleventh International Conference on Learning Representations. 2023.\\\n[8] Schwarzer, Max, et al. \"Data-efficient reinforcement learning with self-predictive representations.\" arXiv preprint arXiv:2007.05929 (2020).\n", "limitations": "Some limitations are discussed in the paper. The discussion can include some potential directions on extending the method to non-stationary tasks.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Exploration with SR has been studied in prior works. The idea of incorporating PR information in the intrinsic reward is interesting.\n2. The experiments for discrete state space are thorough and show that the gains are coming from adding retrospective information with both fixed/learned SR.\n", "weaknesses": "1. The motivation is not very clear. The writing switches between learning continual exploration policy or exploration for singleton tasks. More comments on this are in Questions below.\n2. The paper misses some citations and baselines. There should be discussions on learning exploratory policies that can continually explore and more recent baselines on the same. Comparisons should also be done on environments for non-stationary continuous state space environments. \n3. The results on the Atari benchmark are not very convincing and more insights/tasks are needed for evaluation. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their instructive comments. Please find below our replies to the raised concerns/questions.\n\n- We thank the reviewers for pointing us to the related literature on constructing intrinsic reward based on episodic information and retrospective transitions. SPIE is similar to NovelD in that both methods constructs the intrinsic reward based on the difference of novelty measures at the next state and the current state. However, the difference between SPIE and all three mentioned methods is that the SPIE intrinsic reward is based solely on a global intrinsic bonus, in contrast to the three methods which all leverage (partially) episodic intrinsic bonus. We will include these discussions on the relationship and differences with these methods and included citations to the mentioned papers in the related works section in the camera-ready revision upon acceptance.\n\n\n- Existing intrinsic exploration methods can nevertheless visit bottleneck states. However, consider the uncertainty based methods (e.g., RND and ICM), upon multiple visitation to the bottleneck states, the associated novelty (uncertainty) measure decreases and the agent would generate an intrinsic motivation against visiting the state in the long run. In contrast, the fundamental principle of SPIE is the dynamic balancing between the motivations of visiting bottleneck states and exploring uncertain state. Hence, the implicit motivation towards bottleneck states for making sensible exploratory transitions is sustained irrespective of the agent's perceived knowledge (uncertainty) of the bottleneck states. \n\n- Continual exploration with SPIE is potentially useful even when the task structure (e.g., its connectivity pattern) does not change. For instance, consider an ethologically plausible setting where an animal is performing random foraging in a clustered environment, where the rewards are food that is depleted upon consumption, and new rewards would occur in a different location (with a potential temporal lag). In this case, continual exploration is necessary for fast adaptation to the non-stationary reward location (as demonstrated in Figure 3c-d). However, we note that such \"cycling\" exploratory behaviour and the associated ethological plausibility arises as one of the benefits of SPIE, but is not our main focus in the current paper. We hence do not further study its utility under the continual exploration setting here but it is indeed an interesting direction for future investigation which we will pursue.\n\n- Similar to our argument in the previous point, the continual exploration is not the main focus of the paper. Figure 3c-d and associated discussions aims to demonstrate that SPIE exhibits the potential of showing ethologically plausible continual exploration. We do not interpret SPIE as a state-of-the-art method for solving the continual RL task or procedurally generated tasks, hence we do not provide the corresponding empirical evaluations in the paper. However, we do think this is an important and interesting direction to pursue.\n\n- We thank the reviewer for the suggestion. The average size of the set of unique states visited in a finite-length episode is reported in the rebuttal letter. \n\n- We note that the argument with respect to the asymptotic uniformity only applies to discrete setting. As the reviewer correctly points out, the SF and PF would converge asymptotically and does not lead to continual exploration. However, neither our motivation nor the focus of our empirical evaluation is focused on promoting SPIE as a method for continual exploration or examining its utility in that respect. In all our empirical evaluations under continuous state space, we only focus on single-task settings, hence the asymptotic convergence is beneficial per the asymptotic inconsistency argument from the NovelD paper. \n\n- We argue that DQN-SF-PF does not perform poorly on Freeway and Venture, but it performs comparably with the strongest baselines in these two games. It is hard to probe the exact reason underlying the performance of the agents in Atari games, but we can provide intuitive explanations. One possible reason is that Montezuma's revenge and Private Eye contains more key transition states (bottleneck states) between different \"rooms\" hence the \"bottleneck-seeking\" exploratory behaviour is beneficial in such games.\nWe have now included the evaluation results of DQN-SF-PF (and other baselines) on two more hard-exploration atari games, Gravitar and Solaris. Empirical results indicate that DQN-SF-PF outperforms DQN-SR on both tasks.\nWe do not think SPR is a good baseline to compare against since its motivation does not stem from designing stronger exploration agent, but rather aims at learning better state representation for efficient RL. Moreover, SPR contains more complicated neural architecture and representation learning module than DQN-SF-PF, which leads to unfair comparison. The main aim of our experimental studies is to demonstrate that SPIE is an easy-to-plugin exploration strategy that could yield the same agent to achieve more efficient exploration, rather than showing it beats all state-of-the-art models across all benchmarks.\n\n- In line 127, by \"were the SR matrix to be known...\", we mean that \"assuming the SR matrix is known...\". We do not think it is a typo, however we do apologise for the confusion.\n\n- We thank the reviewer for pointing out additional points for discussing the limits and future works of SPIE, which we will include in the discussion chapter in the camera-ready revision upon acceptance.\n\nWe wish to thank the reviewer again for their thoughtful comments, and we hope the above replies address all concerns/questions raised by the reviewer. If so, we hope the reviewer could adjust their score accordingly. If there is any remaining confusion/concern, please let us know as soon as possible and we are happy to engage in further discussion.\n"}]

Author rebuttal:
We thank all reviewers for their instructive comments for making the paper clearer and more rigorous. There are a number of questions/concerns that are shared by multiple reviewers, which here we provide summarised responses below. We have also attached a rebuttal letter containing additional experiment results requested by the reviewers.

- Main motivation of the paper and the experimental studies:

The main focus of the paper is to propose the SPIE intrinsic exploration framework of combining prospective and retrospective information for more efficient and targeted exploration. Whilst we show additional side benefits that SPIE yields ethologically plausible "cycling" exploratory behaviour, it is not the main focus nor the motivation of SPIE. We provide preliminary experimental studies illustrating the existence of such "cycling" behaviour and discuss its potential application for continual exploration for dealing with non-stationary environments. However, it is by no means our intention to claim or promote SPIE as a state-of-the-art method for dealing with non-stationary continual RL problems. 

Moreover, we wish to clarify that the aim of our empirical evaluations is to demonstrate the improved exploration (and hence learning) efficiency given the dynamic balancing of exploring uncertain states and transitioning into bottleneck states admitted by SPIE. Our experiments comprehensively validates the utility of SPIE framework in tasks with discrete state spaces with tabular value estimates, and in tasks with continuous state spaces using linear and non-linear (deep RL) function approximations. All presented experiments demonstrate that SPIE can be efficiently implemented, with minimal modification to the original agent, whilst yielding significantly better performance. The goal of the paper is to show that retrospective information could and should be utilised for stronger exploration. The conceptual idea can be instantiated with any existing RL agents, and produce state-of-the-art results if needed. 

- The choice of reciprocal form of SPIE objective in continuous settings.

We generalise SPIE to tasks with continuous state spaces by replacing SR/PR with SF/PF. The initial proposal was to use the difference of norms of the SF and PF as is done for the SR in discrete settings. However, we find it hard to set the scaling factor for the SPIE intrinsic reward in this case. We hence adopt the reciprocal form presented in Machado et al., 2018 (last equation on page 5), which we find to yield robust performance on a range of $\beta_{spie}$ values (0.03-0.06). We note that the fundamental principle of SPIE is the combination of prospective and retrospective information for exploration, admitting different instantiations (including those shown in equation 8 and 16 in the main paper). 

- Poor performance of SARSA-SR on pure exploration in grid worlds.

One possible explanation for the poor performance of SARSA-SR is its equivalence to count-based exploration (Machado et al., 2020). Count-based exploration algorithms perform poorly in larger state space such as grid worlds (in contrast to 6 and 7 states for RiverSwim and SixArms) such that the agent preferentially explores local region for an extended time before moving to novel sub-region, hence leading to poor exploration efficiency. 

- More evaluations in deep RL experiments.

We have now provided evaluation results of DQN-SF-PF and baseline agents on all 6 hard-exploration Atari games (Bellemare et al., 2013), which is shown in Table 2 in the attached rebuttal letter. DQN-SF-PF outperforms baseline agents on 4 of the games and yields comparable performance on the remaining 2.

- Missing standard error in linear RL experiment.

We thank the reviewers for pointing out the missing of standard errors in the linear RL experiment (Figure 4c). We have now provided the full evaluations with standard errors in Figure 1a in the rebuttal letter. We note that the reported results for $r_{\text{SF-PF}}$ in this case is from a different set of hyperparameters. We performed a comprehensive hyperparameter search, and the resulting agent with $r_{\text{SF-PF}}$ now yields a significantly higher average completion probability than the agent with $r_{\text{SF}}$ comparing to Figure 4c in the current main paper, further justifying the utility of SPIE.

- Typos and formatting issues.

We thank the reviewers for pointing out various typos, and specifically the width issue with Table 1 in the current main paper. We have now corrected all raised typos and fixed the formatting issues.

We wish to thank all the reviewers again for their thoughtful comments, and we hope the above replies address all concerns/questions raised by the reviewers. If so, we hope the reviewers could adjust their score accordingly. If there is any remaining confusion/concern, please let us know as soon as possible and we are happy to engage in further discussion.


Meta-review: This paper has received very mixed reviews. While some reviewers appreciated the contribution of this work, others have raised some doubts about its motivation and empirical evaluation. The rebuttal seems to have cleared remaining doubts about the experiments, while the main motivation of the paper still seems to be a problem for a reviewer. However, I think that a lack of clarity in the description of the motivation is not a strong reason to reject this paper, and considering the scores, comments, and discussion phase, I tend to accept this paper.

I encourage the authors to address all the comments and to incorporate the recommended improvements in the final version.
Decision: Accept (poster)