Maximum State Entropy Exploration using Predecessor and Successor Representations
Authors: Arnav Kumar Jain
Lucas Lehnert
Irina Rish
Glen Berseth
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Maximum state entropy exploration
Non-Markovian exploration
Successor Representation
TL;DR: We propose $\eta\psi$-Learning algorithm to learn a non-Markovian maximum state entropy exploration policy by combining predecessor and successor representation to estimate the state visitation distribution of trajectory of finite length.

Abstract: Animals have a developed ability to explore that aids them in important tasks such as locating food, exploring for shelter, and finding misplaced items. These exploration skills necessarily track where they have been so that they can plan for finding items with relative efficiency. Contemporary exploration algorithms often learn a less efficient exploration strategy because they either condition only on the current state or simply rely on making random open-loop exploratory moves. In this work, we propose $\eta\psi$-Learning, a method to learn efficient exploratory policies by conditioning on past episodic experience to make the next exploratory move. Specifically, $\eta\psi$-Learning learns an exploration policy that maximizes the entropy of the state visitation distribution of a single trajectory. Furthermore, we demonstrate how variants of the predecessor representation and successor representations can be combined to predict the state visitation entropy. Our experiments demonstrate the efficacy of $\eta\psi$-Learning to strategically explore the environment and maximize the state coverage with limited samples.

Maximum State Entropy Exploration using Predecessor and Successor Representations
Arnav Kumar Jain' Sila--uebee Al Institute Université de Montréal
Lucas Lehnert
Irina Rish Mila Quele AI Institute Université de Montréal
Fundamental Al Research at Meta
Glen Berseth
Mila- Mila-Quebec AI Institute Université de Montréal
Abstract
Animals have a developed ability to explore that aids them in important tasks such as locating food, exploring for shelter, and finding misplaced items. These exploration skills necessarily track where they have been so that they can plan for finding items with relative efficiency. Contemporary exploration algorithms often learn a less efficient exploration strategy because they either condition only on the current state simply rely making random open-loop exploratory moves. In this work, we propose mus-Learning, a method to learn efficient exploratory policies by conditioning past episodic experience move. Specifically, 77u'-Learnin learns an exploration policy that maximizes the entropy of the state visitation distribution of single trajectory. Furthermore, we demonstrate how variants of the predecessor representation and successor represen- tations can be combined to predict the state visitation entropy. Our experiments demonstrate the efficacy of nui-Learning to strategically explore the environment and maximize the state coverage with limited samples.
make the next exploratory
Introduction
Animals and humans are very efficient at exploration compared to their data-hungry algorithms counterparts [36, 28, 50, 51, 12, 14, 65, 52]. For instance, when misplacing an item, a person will methodically search through the environment to locate the lost item. To efficiently explore, an intelligent agent must consider past interactions decide what to explore next and avoid re-visiting previously encountered locations to find rewarding states as fast as possible. Consequently, the agent needs reason over potentially long interaction sequences, a space that grows exponentially with the sequence length. Here, assuming that all the information the agent needs to act is contained in the current state is impossible [43].
In this paper, we present moi-Learnngg an algorithm to learn an exploration policy that methodically searches through task. This is accomplished by maximizing the entropy of the state visitation distribution of single finite-length trajectory. This focus on optimizing the state visitation distribution of single trajectory distinguishes our approach from prior work on exploration methods that maximize the entropy of the state visitation distribution [23, 61, 31, 41, 18]. For example Hazan
al. [23] focus on learning a Markovian policy decision decision-making strategy that is only conditioned
*Correspondence <arnav- <arnav-kumat kumar jain @ mila.quebec> A part of this work was developed while Lucas Lehnert was at the Mila Quebec Al Institute and the Université de Montréal.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(d)
Figure 1: Consider 4 x gridworld for illustration. (a) The agent starts the top left corner and takes a few actions(red arrows show the trace), (b) an optimal trajectory that covers the grid (green arrows) and agent visits a previously observed state in the last step and not able to visit all the states with the limited steps, (d) another sub-optimal trajectory where agent visits observed state at earlier step.
visit all the states without visiting any state twice, (c) sub-optimal trajectory where
on the current state and does consider which states have been explored before. A Markovian policy constrains the agent in its ability to express different exploration policies and typically results randomizing uncertain states to maximize the state entropy objective. While this will lead to uniformly covering the state space in the limit, such behaviors are not favorable for real-world tasks where the agent needs to maximize state coverage with limited number of interactions.
Figure presents a didactic example to illustrate how an intelligent agent can learn to efficiently explore 4 x grid. In this example, the agent transitions between different grid cells by selecting one of four actions: up, down, left, and right. To explore optimally, the agent would select actions that maximize the entropy of the visited state distribution of the entire trajectory. Suppose the agent started its trajectory in the top left corner of the grid (shown in Figure (a)) and has moved to the right twice and made one downward step (indicated by red arrows). At this point, the agent has to decide between one of the four actions to further explore the grid. For example, it could move left and follow the green trajectory as outlined in Figure 1(b). This path would optimal in this example because every state is visited exactly once and not multiple times. However, the top action would lead to sub-optimal trajectory as the agent would visit the previous state. To mitigate sub-optimal exploration, an intelligent agent must keep track of visited states to avoid revisiting states. Although the right action will lead to a novel state the next step, the overall behavior will be sub-optimal as the agent will have to visit state twice to explore the entire grid (depicted in Figures ((c) and (d)). This further requires an agent to carefully plan and account the states that would follow after taking action.
In this work, we propose yea-ning, an algorithm to compute an exploration strategy that method- ically explores within single finite-length trajectory- as illustrated in Figure 1(b). me-LLarning maintains two state representations: predecessor representation [64, to encode past state visitation frequencies and Successor Representation (SR) [13] to predict future state visitation frequencies. The two representations are used evaluate at every time step the decision that leads to covering all states as uniformly as possible. Specifically, for every potential action the agent can take, the SR is combined with the predecessor representation to predict the state visitation distribution for the current trajectory. Then, the action that results in the highest entropy of this state visitation distribution selected for exploration. Furthermore, this exploration policy can deterministic and does not randomize to achieve its maximum state entropy objective.
To summarize, the contributions of this work are as follows: Firstly, we propose mechanism to combine successor [13] and predecessor [64] representations for maximizing the entropy of the state visitation distribution of a finite-length trajectory. To the best of our knowledge, this is the first work using the two representations to optimize the state visitation distribution and learn an efficient exploration policy. Secondly, we introduce mpl-Learning, a method that utilizes the combination of two representations to learn deterministic and non- non-Markovine exploration policies for the finite-sample regime. Thirdly, we discuss how rpi-Learning optimizes the entropy-base based objective function for both finite and (uncountably) infinite action spaces. In Section 5 we demonstrate through empirical experiments that ryl-Leerrning achieves optimal coverage within single finite-length trajectory. Moreover, the visualizations presented in Section 5 demonstrate that mer-Lnnnnn learns

---

an exploration policy that maneuvers through the state space to efficiently explore a task while minimizing the number of times the same state is revisited.
2
Related Work
The domain of exploration in Reinforcement Learning (RL) focuses on discovering an agent's environment via intrinsic motivation to accelerate learning optimal policies. Many existing exploration methods seek novelty by using prediction errors [45, 9, 54, 57] or pseudo-counts [58, 6, 39j. However, such methods add an intrinsic reward signal to improve sample efficiency in single task setting. They do not explicitly learn a policy that is designed to efficiently explore a task, In contrast, we present a method for explicitly learning efficient exploration strategy by maximizing the entropy of single trajectory's ' state visitation distribution. Efficient exploration algorithms can be used to improve learning efficiency in application domains such Meta RL [16, 70, 48, 37], Continual RL [27, 33], and Unsupervised RL [30]. For example, in Meta RI. an agent needs to first explore to identify which of the previously observed tasks it is in before the agent can start exploiting rewards in the current task. In this context, VariBAD [70] maintains a belief over which task the agent is in given the observed interactions. While Zintgraf et al. argue that Bayes-optimal policy implements an efficient exploration strategy, we propose a method that explicitly learns an efficient exploration policy, resulting in discovering rewarding states more efficiently than VariBAD (Section 5).
The core idea behind my--Lernning is the use of the predecessor and successor representations to predict the state visitation distribution induced by a non- Markovian policy for single lenghh trajectory. Instead of using the successor representation for transfer, lifelong learning, or learning one representation that solve set of tasks [3, 69, 4, 8, 38, 56, 22, 5, 32, 34, 1, 62], we the successor representation to estimate the state visitation distribution and maximize its entropy. By using the successor representation in this way, the nos-Learning does not rely density models [23, 31], an explicit transition model [61, 41], or non-parametric estimators such as k-NN [42]. In the following sections we will discuss how Lei-Learning learns a deterministic exploration policy and does not rely on randomization techniques [42, 31] or mixing multiple policies to manipulate the state visitation distribution [31, 233. Moreover, Mutti et al. [44] provide theoretical analysis proving that efficient (zero regret) exploration is possible with deterministic non- Non-Markovian policy but computing such a policy is NP-hard. In this context, mo-Leanning is our knowledge the first algorithm for computing such an efficient exploration policy.
3 Maximum state entropy exploration
We formalize the exploration task as a Controlled Markov Process (CMP), a quadruple M (S, A. p. μ)) consisting of (finite) state space S, a (finite) action space A, a transition function p specifying transition probabilities with p(s, s') = P(s'|s, [s, a), and a start state distribution specifying probability of starting a trajectory at state with j(s)). A trajectory is sequence
= (81, 00, ..., 0h-1,8h) 1h) ) of some length h that can be simulated in CMP. A policy л specifies a probability distribution or density function over the action space that is sampled when selecting actions and simulating a trajectory in a CMP. This policy definition include deterministic policies: For discrete action spaces a specific action is selected with probability one and for uncountably infinite action spaces the policy models a delta-dirac density function. In algorithms such as Q-learning [1 I], the policy is conditioned on the task state and specifies the probabilities of selecting a particular action. However, as illustrated in Figure 1, the past trajectory (red arrows) determines which next action leads to the best exploratory trajectory. Consequently, we consider policies that are functions of trajectories rather than just states.
The state visitation distribution of trajectory Th = (81, (i,,..,, -h-1, .h, 81)) of length à can be formally expressed in probability vector by first encoding every state 8t as one-hot bit vector es, Using this one-hot encoding, the h-step state visitation probability vector of the trajectory тh can computed by marginalizing across the time steps:
h
Ex,T
(1)e,,
(1)
3

---

where y N + [0, is the discount function (we denote the set of positive integers with N), such that E y(t) 1. Using the normalization in the discount function is necessary it ensures that & is a probability vector. We note that this use of a discount function is distinct from using a discount factor in common RL algorithms such as Q-learning but using a discount function is necessary we will elaborate in the following section.The expected state visitation distribution for a policy я can be obtained by generating multiple trajectories using オ and computing the average across them get the expected state visitation distribution, denoted by E, (7.7).
An optimal exploration policy would achieve similar visitation frequency for each state, illustrated in Figure 1(b) where the optimal trajectory traverses every state once within the first 15 steps. For this trajectory the vector Σ.,y would encode uniform probability vector, given (t) à for any t. In fact, an optimal exploration policy nt" maximizes the entropy of this probability vector and solves the optimization problem
π E arg max H (E, yE
where the expectation is computed across trajectories that are simulated in a CMP and follow the policy n.3 3 In the remainder of the paper, we will show how optimizing this objective leads to the uniform sweeping behavior illustrated in Figure and the agent learns to maximize the entropy of the state visitation distribution in a single finite length trajectory. In the following section, we describe how mei-Lernnig optimizes the objective in Equation 2.
4 Tru-Learning
To learn an efficient exploration policy, we need to estimate the state visitation history and predict
the distribution over future states. Consider trajectory ($1, 01, ..., ST ar- $1 -. 8%.). At an intermediary step T. we denote the T 1-step prefix with T-r-1 = ($1, Q1. 8T-1) and
the suffix starting at step T with Tr: (ST. aT.... d4-1, s4).. Using this trajectyyy notation, the discounted state visitation distribution in Equation can be written as
T-1
ST. Σ (t)ee,, 1=1
+ Σ (t)e...
(3)
T=
Assuming the scenario presented in Section 3, suppose the agent has followed the trajectory T.r until time step T. At this time step, the agent needs to decide which action ar leads covering the state space as uniformly as possible and maximizes the entropy of the state visitation distribution. The expected state visitation distribution for policy can be expressed by conditioning on the trace T.r and potential action E AA:
E E,,x
TrP, oT
ET
(t)es,
(t)es,
T.T,0 or
(4)
T-1
7()e,. + Err+uo
Σ (1)) T.T, ar
(5)
= (T:r,a7)
where the vector 7(TTT-1) is variant of the predecessor representation [64, 2] and the vector (TTT,, aT) a variant of the successor representation (SR) [13]. Splitting the expected state visitation distribution into vector and s as outlined in Equation 5 is possible because assuming a discount function y as defined in Section 3. At time step T, the two representations can be added together to estimate the expected state visitation probability vector. Simulating the proposed algorithm is analogous to effectively drawing Monte-Carlo samples from the expectation at different steps T to learn a SR and predict the expected visitation frequencies of +,.
The predecessor representation vector (T.T-1)) can still be estimated incrementally similarly to the eligibility trace in TD(A) algorithm [59] (but with different weighting scheme that uses the discount function 7). While the definition of the vector (TTT)) is similar to the definition of eligibility
'Here, we consider the Shannon entropy H (p) = E, p. log P. where the summation ranges over the entries of the probability vector p.

---

traces [60. Chapter 12], we do not use the predecessor trace for multi-step TD updates to learn more efficiently. Instead, the vector TTT--1 estimates the visitation frequencies of past states the predecessor states decide which states to explore next.
While the predecessor representation be maintained using an update rule because the observed states are known, predicting future state visitation frequencies is more challenging. A potential solution is exhaustively search through all possible sequences of trajectories starting from the current state. This is computationally infeasible and requires a dynamics model of the environment. Moreover, such a model is not always available, and learning them is prone to errors that compound for longer horizons [49, 26]. To this end, we learn variant of the successor representation (SR), which predicts the expected frequencies of visiting future or successor states under a policy [13]. In contrast to previous methods which learn successor representation (SR) conditioned on the current state [13, 3], Ler-Ing conditions the SR on the entire history of states, given by
h
き" (T:I, AT) = =E,, BBy 11:
Σ (t)ee..
T.T QT
(6)
Conditioning the SR on the trajectory T:T is necessary because policy x is also conditioned on T.T and therefore the visitation frequencies of future states depend on T:T. Moreover, the expectation evaluates all possible trajectories after taking action or at time T and following policy π afterward. We discuss in Appendix C how the SR vectors are approximated using a recurrent neural network.
We saw in Equation 5 that the predecessor representation and successor representation can be combined predict the state visitation distribution for a policy π and a trajectory-prefix T.T. myú- Learning uses the estimated state visitation distribution to compute the entropy term in the objective defined in Equation 2. Specifically, the utility function Qespi approximates the entropy of the state visitation distribution for an action @r at every time step. By defining
Qexpi(T.r, or) = H (n(T.r-1) + 26" (T:I,ar)
the action that leads to the highest state visitation entropy is assigned the highest utility value. Notably, the proposed Q-function differs from prior methods using the SR, as we neither factorize the reward function [3, 4, 8, 62] nor use the SR for learning a state abstraction [32]. Optimizing the exploration Q-function stated in Equation
challenging as depends on the SR that itself depends on the policy æ which changes during learning. Furthermore, Guo et al. [18] show that the Shannon-entropy based objective difficult to directly optimize using gradient- methods (due to the log term inside an expectation) [31, 47, 18]. In contrast, we outline in the following paragraphs how the entropy objective in Equation 7 can be directly optimized using either a Q-learning style method or method based on the Deterministic Policy Gradient [55] framework for finite and infinite action spaces, respectively.
Finite action space framework Since the predecessor representation is fixed for a given trajectory T:,, optimizing the Q-function defined in Equation 7 boils down to predicting the optimal SR for a given history T.r. Similar to prior Successor Feature learning methods [3, 4, 333, we approximate the SR with parameterized and differentiable function the and use loss based on a one-step temporal difference error. Given an approximation the the SR prediction target is obtained by the current state embedding and SR of the optimal action at the next step:
( d/++)) = esr + 7T + 1) (T.T+1, d7+1);
(8)
where T. obtained by adding action ar and the received next state ST+11 to the trajectory T. Analogous to Q-Learning, the optimal action at the next step is specified by
a = arg max Qexpi (T.T+1.a). a
(9)
Being greedy with respect to these entropy values to estimate the target leads to improving the policy which in turn finds the SR for the optimal policy. (Appendix A presents convergence analysis of this method in dynamic programming setting.) Then, the function the is optimized using gradient descent on the loss function LSR. given by
LsR = (ibe(TTr,)) ar) - UUTTTT 111
(10)
where gradients are not propagated through the target ((TT++ dr+1). Finally, the optimal policy selects actions greedily with respect to the Qespi function. Algorithm describes the training procedure for the proposed variant for finite action spaces.
5

---

Infinite action space framework Directly obtaining gradient estimates of objective defined in Equation 2 is challenging because of the expectation term the non-linear logarithmic term. Previous approaches have used alternative optimization methods [31, 47] or resorted to a simpler noise- contrastive objective function [18]. In contrast with prior algorithms, we derived an 7pe-Learnnng variant for infinite action spaces that optimizes an actor-critic architecture using policy gradients to maximise the maximum state entropy objective. The agent uses an actor-critic architecture where actor and critic networks are conditioned on the history of visited states. The actor TT((T) (T) is parameterized with a parameter vector Il and is a deterministic map from a trajectory to an action. The critic predicts the SR to estimate the utility function conditioned finite action space variant, the predecessor representation is fixed for a given trajectory and the network has to predict SR the T, a) for a given trajectory т and action o. Here, the target value of SR to update the critic is specified by the action obtained using the policy 47+1 = [T(TTT+)), given by
given trajectory and action. Similar to the
y Cer + (T +1)+11)pg0 1) (TT+1,11T))))
(11)
The critic is trained with the same loss function CSR defined in Equation 10, where the gradients are not propagated through the target. The actor is optimized to maximize the estimated utility function (Equation 2). Since the actor is deterministic, policy gradients are computed using an adaptation of the deterministic policy gradient theorem [55]. Because the actor network has no dependency on predecessor trace (which depends the observed states only), gradients for the actor parameters are obtained by applying chain rule leading to the following gradient of Equation 7 (please refer Proposition 2 for more details the derivation):
V (Tpp = EToP Σ 2
(12)
a=x.((
where 2; = = log(m(T:.))) + (T, (T)) - 1 is the multiplicative factor for state i, and depends on the expected probability of visiting state. The factor 2; can take values between between -1 and 00, with positive values of high magnitude for states with low visitation probability and negative values for state with high probability of visitation. Thus, the factor 2; scales the policy gradients to maximize the entropy of the state visitation distribution. In Algorithm 3 we outline the training procedure for the infinite action space framework.
Experiments
To analyze and test if reei-Lerning learns efficient exploration policy, evaluate the proposed method on a set of discrete and continuous control tasks. In these experiments, we are recording a set of different performance measures access if the resulting exploration policies do in fact maximize the entropy of the state visitation distribution and if most states are explored by ryë-Learning. The following results demonstrate that by maintaining a predecessor representation and conditioning the SR on the simulated trajectory prefix, the mö-Learning agent Iearns a deterministic exploration policy that minimizes the number of interactions needed visit all states. In addition, we expand our method to continuous control tasks and demonstrate how mei-Lerrning can efficiently explore in complex domains with infinite action space. Our method is ideal for searching out rewards in difficult sparse reward environments. We compare mu--Lerrning which learns to explore an environment as efficiently as possible, to recent meta-RL RL methods [70] that aim learn how to optimally explore an environment to infer the rewarding goal state. Lastly, we show the applicability of rnj-Learning on standard RL tasks where the extrinsic rewards are sparse and present how the proposed method can be combined with existing algorithms.
Environments: We experiment with different tasks with both finite and infinite action spaces. The ChainMDP and RiverSwim [58] is a six-state chain where the transitions are deterministic or stochastic, respectively. In these tasks a Markovian policy cannot cover the state space uniformly because the agent has to pace back and forth along the chain, visiting the same state multiple times. For the RiverSwim environment a ota-ssationary policy, a policy that is a function of the time step. cannot optimally cover all states because non non-determinism in the transitions can place the agent into different states at random. Furthermore, we include the 5 x grid world example used in Figure 1. We also test 7jü-Learning on two harder exploration tasks-the TwoRooms and FourRooms domains, which are challenging because it is not possible to obtain exact uniform visitation distribution due to the wall structure. For continuous control tasks, we evaluate Reacher and Pusher tasks, where the

---

ChainMDP
RiverSwim
GridWorid
TucRooms
Four
1.75
3.25
1.73
3.00
1.23
2.75
1.23
1.00
1.00
2.50
0.75
0.75
2.0
2.23
0.30
200
420
1020
250
403
620
800
1000
400
900
500
1000
2003
420
1000
500
1000
1500
2000
2503
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.0
0.4
0.4
0.4
0.2
0.2
0.2
200
400
500
000
1000
200
400
020
000
1000
200
400
900
200
1000
P00
202
420
600
800
1000
500
1000
1502
2000
2502
Search Complttee lime
600
300
700
100
200
100
200
450
600
1000
200
603
600
800
1000
%
200
400
900
800
1000
203
450
600
400
1000
500
1000
1903
2000
2003
MaxFFit
earming
Figure 2: Comparison of neé-LLarning and MaxEnt [23] three metries: Entropy (top row) of state visitation distribution, State Coverage (middle row) representing the fraction of state space visited, and Search Completion Time (bottom row) denoting steps taken cover the state space.
agent has a robotic-and arm with multiple joints. The task is to maximize the entropy over the locations covered by the fingertip of the robotic-arm. Appendix F provides more details on the environments and the hyper-parameters are reported in Appendix G.
Prior Methods: To our knowledge, existing work focusses on learning Markovian exploration policies [43]. We use MaxEnt [23] as baseline agent for our experiments because this method optimizes a similar maximum entropy objective as nu--Leannig-
the difference that MaxEnt learns a Markovian policy and resorts to randomization to obtain a close to uniform state visitation distribution. We have also compared with MEPOL [42] on continuous control tasks which leans Markovian policy and uses kNN-based estimators to compute the entropy. A comparison with SMM [31] is skipped because the method optimizes a similar maximum entropy objective with a Markovian policy and cannot express the same exploration behaviour as npei-Lerrnin.
Entropy measures a method's ' ability to have similar visitation frequency for each state in the state space. This signifies the gap between the observed state visitation distribution and the optimal distribution that maximizes the entropy term. The Entropy metric is computed using the objective defined in Equation 2 over a single trajectory generated by the agent. A constant discount factor of (t) = a/ is used to obtain the state visitation distribution during evaluation. An agent can maximize this measure without actually exploring all states of an environment-a desirable property for RL where rewards may be sparse and hidden in complex to-reach states. We record the state coverage metric which represents the fraction of states in the environment visited by the agent least once within a trajectory. Lastly, we want agents to explore the state space efficiently. For example, an optimal agent can sweep through the gridworld presented in Figure I with search completion time of 15 steps Figure 1(b) shows an optimal trajectory). The search completion time metric measures the steps taken to discover each state in the environment. All results report the mean performance computed over 5 random seeds with 95% confidence intervals shading.
Evaluation Metrics:
Quantitative Results: Figure 2 presents the results obtained for mui-Larnning and MaxEnt [23]. Compared MaxEnt, which learns a Markovian policy, nyo-Learning achieves 20-50% higher entropy. This indicates that the MaxEnt algorithm by learning a Markovian and stochastic policy was randomizing at certain states which lead to sub-optimal behaviors. The performance gain was more prominent in brsed environments because the MaxEnt agent was visiting some states more frequently than others, which are harder to explore efficiently. Furthermore, high entropy values suggest that the agent visits states with similar frequency in the environment and does not get stuck at a particular state. We attribute this behavior of rpu- Learning to the proposed Q-function that picks action to visit different states and maximize the objective.
7

---

(%,
[-+
((L)
(++)
(a)
(b)
Figure 3: (a) Heatmap of state visitation distribution by unrolling a trajectory using MaxEnt (left) and Lei-Learning (right) on TwoRooms and FourRooms environments. (b) Visualization of learned SR of each action (denoted with (²))) at time steps T = 7, 14 for trajectory using mys-Lerrning on 5 x 5 grid. (s, a) denotes the state (black) and action taken by the agent (direction of white arrow), is the predecessor representation till time T (higher values have darker shade)
Figure 2 also shows that rpi-Learning achieves optimal state coverage across environments exempli- fying that mi--Larnnng while maximizing the entropic measure also learns to cover the state space within single trajectory. However, the bascline MaxEnt was not able to discover all the states in the environment. MaxEnt was unable to visit all the states ChainMDP and RiverSwim environments with trajectory length of 20 and 50, respectively. Moreover, the state coverage of MaxEnt 50-60 % on the harder TwoRooms and FourRooms tasks, where the agent has to navigate between different rooms and is required to remember the order of visiting different rooms. These results reveal that Markovian policy limits an agent's 's ability to maximize the state coverage in a task. The proposed method also outperformed the baseline on the search completion time metric across all environments. Notably, on ChainMDP, the 5 x 5 gridworld, and TwoRooms environments, upp-Learning converged within 500 episodes. However, nyë-LLarning did not achieve optimal search exploration time on the FourRooms environment as it missed a spot in room and resorted to it later in the episode.
around
To further understand the gains offered by -ea-nnnnn visualized the state visitation distributions on a single trajectory (in Figure 3(a)). On the TwoRooms environment, mýs-Lernning had similar density the states in both the rooms, where the density is more around the center. This is because the agent was sweeping across rooms alternatively. yui-Learning showed a better-visited state distribution on the FourRooms environment with more distributed density across states. However, MaxEnt was not visiting all states and also visited a few states more frequently than others, elucidating the lower performance on entropy and state coverage. We further visualized the learned SR to if ryú-- Learning learns a SR for the optimal exploration policy through generalized policy improvement [3]. For this analysis, we sampled a trajectory on 5 x 5 gridworld. Figure 3(b) reports the heatmaps of the learned SR vector for each action at different steps in the trajectory. We observe that the SR vector for each action has lower density on the states already observed in the trace. This exemplifies that the learned SR captures the history of the visited states that further aids in taking actions to maximize the entropy of state visitation distribution. We also study if MaxEnt can show similar gains when trained with a recurrent policy (Appendix 1.1) and compared the agents when evaluated across multiple trajectories (Appendix I.2).
The efficacy of rrě-Learning is further tested on environments with infinite action space. Figure 4(a) reports the Entropy and State Coverage metric Reacher and Pusher environments, where vpei-Learning outperformed the baseline MaxEnt on both metrics. The gains are more significant on the Pusher environment which is a harder task because of multiple hinges in the robotic-arm. The proposed method mu-Learning achieves close to 90% coverage in both environments, whereas the MaxEnt had only close to 50% and 40% coverage on Reacher and Pusher environments, respectively. In Figure 4(b), heatmaps of the state visitation density for single trajectory shows that Le-LLarming has more uniformly distributed density compared MaxEnt. The Pusher environment has high density at the top-right corner of the grid denoting the time taken by the agent to move the fingertip to other locations from starting state. Notably, the proposed method mp--Learning has lower density at the starting state and we believe that conditioning on the history of states is guiding the agent to move the robotic-arm to other locations to maximize the entropy over the state space. In Appendix 1.5, visualization of rolled-out trajectory generated using ryu- ru-LLerrning is
Continuous Control tasks:

---

Reacher
5x5 idworld
0.12
1.5
0.30
10
207
22"
12*
101
0.08
3.8
0.09
Eproddes
Erolnnsent
Random
Mastnt
MEFOL
Leornig
Vori40
Ap Leamingg
(b)
Figure 4: (a) Comparison of ryu Learning with Random policy, MaxEnt [43], and MEPOL [42] on Reacher and Pusher tasks (b) Heatmaps of visitation distribution of MaxEnt (top) and rei-Lernnnng (bottom), (c) comparison with VariBAD [70] on State Coverage and Goal Search Time metrics.
presented showing that the agent learns to efficiently maneuver the fingertip the robotic-arm to different locations in the environment.
Comparison with Meta-RL: A question central to Meta-RL [16, 70, 37] is the ability quickly explore a task and find rewarding states in complex tasks where the rewards are sparse. In this context, Zintgraf al. [70] present the VariBAD method, which maintains belief over different tasks to infer the optimal to discover rewarding states quickly. Similar to VariBAD, the predecessor representation n in ryú- Learning keeps track of which states have been explored and which states are not explored. Figure 4(c) compares the exploration behaviour of upu-Learning to VariBAD: terms of the State Coverage and Goal Search Time metric, 7piiLearning outperforms VariBAD significantly because mpl-Learning designed to optimize the entropy the state visitation frequencies of a single trajectory instead of performing Bayes-adaptive inference across task space. We refer the reader to Appendix H for more details on this experiment.
to efficient exploration behaviour that enables the agent
m in Sparse Reward Tasks: Sparse reward environ- ments pose a challenge where an agent has to discover the reward function by visiting different regions of the state space. Through this experiment, we demonstrate how an agent can leverage 7/0-- Learning as exploratory bonus and improve its efficiency in such tasks. The experiment is conducted on Sparse Mountain- Car environment where the agent receives positive reward upon reaching the goal position. This is hard because the agent needs to plan to visit different positions in the environment. We have used TD3 [17] as the baseline algorithm for this task. To compare with
Sparse MountainCar
100
Retur
20
8.0
0.2
0.4
200
leading exploration methods, add TD3 combined with Count-
Based [6] and First- Prrst-Occupnccy based [40] to the baselines. It is
Eokode Length
be noted that we have used these methods as episodic bonuses as described in [67]. We also propose a variant of TD3 equipped with the proposed method and call it TTD3-nj/-Learning
1000
where we
learn two critics to estimate the sum of extrinsic rewards and the entropy of state visitation distribution (Equation 7). Appendix describes the experimental setup in more detail and Algorithm 4 provides the pseudocode of the proposed variant. The evaluation is done across two metrics- Average Return and Average Episode Length denoting the steps taken to reach the goal state. Figure 5 presents the results where the proposed method outperforms the baseline algorithms and is sample-efficient at learning the task.
8.0
0.2
0.3
Environmann Staps millions)
TD3-Finst
TD3
Learminng
To3-Count
Figure 5: Results on Sparse
Mountain Car environment.
TD3 combined with First-Occupancy based intrinsic reward performed better than Count-Based bonus but still takes twice number of steps as the proposed method to solve the task. This shows that the proposed method can improve sample efficiency in standard RL tasks, especially with sparse

---

rewards. We leave scaling the proposed method with leading architectures [21, 25, 53] to more challenging tasks for future research.
Discussion
To explore efficiently, an intelligent agent needs to consider past episodic experiences to decide on the next exploratory action. We demonstrate how the predecessor representation encoding of past state visitations- can be combined with the successor representation state visitations learn efficient exploration policies that maximize the prediction of future entropy. Across a set different environments, we illustrate how neel-Lernnng consistently reasons across different trajectories to explore near optimally-4 a task that is NP-hard [43].
To the best of our knowledge, mpv-Learning the first algorithm that combines predecessor and successor representations to estimate the state visitation distribution. Furthermore, Ml-Learning learns a non-Markovian policy and can therefore express exploration behavior not afforded by existing methods [23, 31, 42, 18). To further increase the applicability of nyě-LLarning, one interesting direction of future research is to extend yyš-Learning either partially observable or complex such as images. This is challenging because the agent has to learn an embedding of state observations that capture only the relevant components of the state space to maximize the entropy. We believe a promising approach would be to leverage the idea of Successor Mcasures (SM) [62, 63, 15] which have shown promising results when scaled to high- dimensional inputs like images. Furthermore, the presented approach can be also used for designing other algorithms that control the state visitation distribution. An application is goal-conditioned RL, where the agents need to minimize the KL divergence between visitation distribution of policy and goal-distribution [31, 47]. Another application is Safe RL [66] where agents receive a penalty upon visiting unsafe states avoid observing them.
POMDP environments where states are
We study reinforcement learning, which aims to enable autonomous agents acquire search behaviors.
This study of developing exploration behaviors in reinforcement learning is guided by a fundamental curiosity about the nature of autonomous learning; has a number of potential practical applications and broad implications. First, autonomous exploration for pre-training in general, can enable autonomous agents to acquire useful skills with less human intervention and effort, potentially improving the feasibility of learning-enabled enabled robotic systems. Second, the practical applications that we illustrate, such as applications to continuous environments, can accelerate reinforcement learning in certain settings. Specific to method, finite length entropy maximization may also in the future offer a useful tool for search and rescue, by equipping agents with an objective that causes them to explore space systematically to locate lost items. However, these types of reinforcement learning methods also have a number of uncertain broad implications: agents that explore the environment and attempt acquire open-ended skills may carry out unexpected or unwanted behaviors, and would require suitable safety mechanisms of their own during training.
Acknowledgements
The authors would like to thank Harley Wiltzer for his valuable feedback and discussions. The writing of the paper also benefited from discussions with Darshan Patil, Chen Sun, Mandana Samiei, Vineet Jain, and Arushi Jain. The authors want to acknowledge funding support from NSERC and CIFAR, AJ and IR acknowledge the support from Canada CIFAR AI Chair Program and from the Canada Excellence Research Chairs (CERC) program. The authors are also grateful to Mila (mila.quebec) IDT, NVIDIA and Digital Research Alliance of Canada for computing resources.
References
[1] Majid Abdolshah, Hung Le, Thommen Karimpanal George, Sunil Gupta, Santu Rana, and Svetha Venkatesh. A new representation of successor features for transfer across dissimilar environments. In International Conference on Machine Learning, pages 1 1-9, PMLR, 2021.
[2] Dunean Bailey and Marcelo Mattar, Predecessor features. arXiv preprint arXiv:2206.00:: 0030.3 2022.
10

---

[3] André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado P van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30, 2017.
[4] Andre Barreto, Diana Borsa, John Quan, Tom Schaul, David Silver, Matteo Hessel, Daniel Mankowitz, Augustin Zidek, and Remi Munos. Transfer in deep reinforcement learning using successor features and generalised policy improvement. In International Conference on Machine Learning, pages 501-510. PMLR, 2018.
[5] André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences. 117748):30079-30087, 2020.
[6] Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pages 1471-1479, 2016.
[7] Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
[8] Diana Borsa, Andre Barreto, John Quan, Daniel J. Mankowitz, Hado van Hasselt, Remi Munos, David Silver, and Tom Schaul. Universal successor features approximators. In International Conference on Learning Representations, 2019. URL https://openrevvie http://pppnreiieeeeeeeeefrrr net/forum? id-S1VwjiRcKX.
[9] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019. URL
https://openreeviet wwt/foorutiddtiiieoooee. 2d-11113R15dm11
[10] Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014.
[11] JCH Christopher. Watkins and peter dayan. Q-Leamnng. Machine Learning, 8(3)229--292.
1992.
[12] Andy Clark. A nice surprise? predictive processing and the active pursuit of novelty. Phe- nomenology and the Cognitive Sciences, 17(3):521-534 2018
[13] Peter Dayan. Improving generalization for temporal difference learning: The successor repre- sentation. Neural computation, 5(4)6613-624, 1993.
[14] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847::580-586 2021.
[15] Jesse Farebrother, Joshua Greaves, Rishabh Agarwal, Charline Le Lan, Ross Goroshin, Pablo Samuel Castro, and Mare G Bellemare. Proto-value networks: Scaling representa- tion learning with auxiliary tasks. In The Eleventh International Conference on Learning Representations, 2023. URI. https: haapp:///ppeerevieeeee wttp:/neee/fffoooe http:/rrrmmmmoo00sstsssl.l 1d==
[16] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In International conference machine learning, pages PMLR, 2017.
[17] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Jennifer Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1587-1596. PMLR, 10-15 Jul 2018.
[18] Zhaohan Daniel Guo. Mohammad Gheshlaghi Azar, Alaa Saade, Shantanu Thakoor, Bilal Piot, Bernardo Avila Pires, Michal Valko. Thomas Mesnard, Tor Lattimore, and Rémi Munos. Geometric entropic exploration. arXiv preprint arXiv:2101.0200
2021.
[19] Tuomas Haarnoja, Aurick Zhou, Pieter 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
[20] Danijar Hafner, Timothy P Lillicrap. Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. In International Conference on Learning Representations, 2021. URI https: / /ttee:///oppoee http///ppeeeeieeeeeeee/ee wttp://ormm..ddo0oarrrraeeaeoeoa

---

[21] Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering diverse domains through world models. arXiv preprint TrXi::2301.04044 2023.
[22] Steven Hansen, Will Dabney, Andre Barreto, David Warde-Farley, Tom Van de Wiele, and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. In Inter- national Conference on Learning Representations, 2020. URL https://openreett net/ forum?1@-BBJAHHrrYYY.
[23] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 2681-2692 PMLR, 09-10 15 Jun 2019. URL httpp::::ppocceedaiaiieee mlr. wtwpppess//////aeeee 1 html.
[24] Mikael Henaff, Minqi Jiang, and Roberta Raileanu. A study of global and episodic bonuses for exploration in contextual MDPs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning. volume 202 Proceedings of Machine Learning Research, pages 12972-12999, PMLR, 23-29 Jul 2023.
[25] Arnv Kumar Jain, Shiva Kanth Sujit, Shruti Joshi, Vincent Michalski, Danijar Hafner, and Samira Ebrahimi Kahou. Learning robust dynamics through variational sparse gating. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL -*QWBa.
net/ costs/forumiid
[26] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. Advances in Neural Information Processing Systems, 32, 2019.
[27] Khimya Khetarpal, Matthew Riemer, Irina Rish, and Doina Precup. Towards continual rein- forcement learning: A review and perspectives. Journal of Artificial Intelligence Research, 75: 1401-1476, 2022.
[28] Celeste Kidd and Benjamin Hayden. The psychology and neuroscience of curiosity. Neuron, 88(3):449-4611 2015.
[29] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6980, 2014.
[30] Michael Laskin, Denis Yarats, Hao Liu, Kimin Lee, Albert Zhan, Kevin Lu, Catherine Cang, Lerrel Pinto, and Pieter Abbeel. URLB: Unsupervised reinforcement learning benchmark. In Thirty-fishh Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL https://openrreiie. wttpeeewwwwwwwweeeeeeeeeeeeeeeee wwt./eeefruuuu ?id=1wrPkQP
[31] Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Rus- lan Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arXiv:1906.05274 2019.
[32] Lucas Lehnert and Michael L Littman. Successor features combine elements of model-free and model-based reinforcement learning. J. Mach. Learn. Res., 21:196-1, 2020.
[33] Lucas Lehnert, Stefanie Tellex, and Michael L Littman. Advantages and limitations of using successor features for transfer in reinforcement learning. arXiv preprint arXiv: 000..000111000 0002, 2017.
[34] Lucas Lehnert, Michael L Littman, and Michael J Frank. Reward-predictive representations gen- eralize across tasks in reinforcement learning. PLoS computational biology, (((10);e1008311 2020.
[35] Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement leam- ing. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, 2016.
[36] Jordan Litman. Curiosity and the pleasures of learning: Wanting and liking new information. Cognition& & emotion, 19(6)7933-8) 814, 2005.
12

---

[37] Evan Z Liu, Aditi Raghunathan, Percy Liang, and Chelsea Finn. Decoupling exploration and exploitation for reinforceent learning without sacrifices. In International conference on machine learning. pages 6935-6935. PMLR, 2021.
[38] Chen Ma, Junfeng Wen, and Yoshua Bengio. Universal successor representations for transfer reinforcement learning. arXiv preprint arXiv: /804. 03758, 2018.
[39]
Marlos Machado, Mare G Bellemare, and Michael Bowling, Count-based exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5125-5133, 2020.
[40] Ted Moskovitz, Spencer R Wilson, and Maneesh Sahani. A first-occupancy representation for reinforcement learning. In International Conference on Learning Representations, 2022. URL httpps://openrevies..o www.eeiwwwweeeeeeeeeeeeeeeeeeeee fotooummdddoo
[41] Mirco Mutti and Marcello Restelli. An caaenniicall-motivataet approach for learning highly exploring and fast mixing policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5232-5239, 2020.
[42] Mirco Mutti, Lorenzo Pratissoli, and Marcello Restelli. Task-agnostic exploration via policy gradient of a parameeriii state entropy estimate. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9028-9036, 2021.
[43] Mirco Mutti, Riccardo De Santi, and Marcello Restelli. The importance of non-markovianity in maximum state entropy exploration. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 16223- 16239. PMLR, 17-23 Jul 2022. URL https: pttpe///oocceeeesee/eeeee/o mlr, .rress/s//// v162/mutti22a, html.
[44] Mirco Mutti, Mattia Mancassola, and Marcello Restelli. Unsupervised reinforcement learning in multiple environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7850-7858, 2022.
[45] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity- exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition Workshops, pages 16-17, 2017.
[46] Darshan Patil, Ali Kalahroui,, Hadi Nekoei, Sai Krishna Gottipati, Mohammad Reza Samsami, Kshitij Gupta, Sriyash Poddar, Artem Zholus, Maryam Hashemzadeh, Xutong Zhao, and Sarath Chandar. Rlhive. https: //gttub.. com/ haam//hhndar--ae latl/labb/Rleeeee 2023,
[47] Vitchyr Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering self-supervised reinforcement learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 7783-7792 PMLR, 13- 18 Jul 2020. https: RRLLhttp::/0 htttp:://proceedings wwm. Silur.pres///i peress/vv19/gee hwtp///og//////...////// html.
URL
[48] Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. Efficient off-policy meta-reinforcement learning via probabilistic context variables. In International conference on machine learning, pages 5331-53400 PMLR, 2019.
[49] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth interna- tional conference on artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
[50] Jürgen Schmidhuber. Curious bodeel-billingg control systems. In (Proceedings] 1991 IEEE International Joint Conference on Neural Networks, pages 1458-1463, IEEE, 1991
[51] Jürgen Schmidhuber. Simple algorithmic theory of subjective beauty, novelty, surprise. inter- estingness, attention, curiosity, creativity, art, science, music, jokes. Journal of the Society of Instrument and Control Engineers, 48(1):21-33) 2009.
[52] Jürgen Schmidhuber. Formal theory of creativity, fun, and intrinsic motivation (1990-2010). IEEE transactions autoromous menial development, 2(3):230 2010.
[53] Max Schwarzer, Ankesh Anand, Rishab Goel, R Devon Hjelm, Aaron Courville, and Philip Bachman. Data-efficient reinforcement learning with self pelf-predictive representations. In Inter- national Conference on Learning Representations, 2021. URL. htt.tts::/pppreeiiiiii net/ forum?id--uCQEP2wBa..
13

---

[54] Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning explore via self-supervised world models, In ICML, 2020.
[55] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pages 387-395. Pmir, 2014.
[56] Shamane Siriwardhana, Rivindu Weerasakera, Denys JC Matthies, and Suranga Nanayakkara. Vusfa: Variational universal successor features approximator to improve transfer drl for target driven visual navigation. arXiv preprint arXiv: 2019.
[57] Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv:/507.0000 000440 2015.
[58] Alexander Strehl and Michael I. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):130--133,, 2008.
[59] Richard S Sutton, Learning to predict by the methods of temporal differences. Machine learning. 3(1):9-44, 1988.
[60] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[61] Jean Tarbouriech and Alessandro Lazaric. Active exploration in markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 974-982. PMLR, 2019.
[62] Ahmed Touati and Yann Ollivier. Learning representation to optimize all rewards. Advances in Neural Information Processing Systems, 34:13-23, 2021.
[63] Ahmed Touati, Jérémy Rapin, and Yann Ollivier. Does zero-shot reinforcement learning exist? In The Eleventh International Conference on Learning Representations, 2023. URL https:
[64] Hado van Hasselt, Sephora Madjiheurem, Matteo Hessel, David Silver, André Barreto, and Diana Borsa. Expected eligibility traces. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9997-10005, 2021.
[65] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A new challenge for reinforcement learning. arXiv preprint 1rXiv:1708.0444 04782, 2017.
[66] Nolan C Wagener, Byron Boots, and Ching-An Cheng. Safe reinforcement learning using advantage-band based intervention. In International Conference on Machine Learning, pages 10630- 10640. PMLR, 2021.
[67] Kaixin Wang, Kuangqi Zhou, Bingyi Kang, Jiashi Feng, and Shuicheng YAN. Revisiting intrinsic reward for exploration in procedurally generated environments. In The Eleventh International Conference on Learning Representutions, 2023. URL https:// //ppr//veeeeeeeee..
net/forume met/forum?id=:33K33 3d=j33K33xxyydt"
[68] Yang Yu, Zhiqiang Gong, Ping Zhong, and Jiaxin Shan. Unsupervised representation learning with deep convolutional neural network for remote sensing images. In International conference on image and graphics, pages 97-108. Springer, 2017.
[69] Jingwei Zhang, Jost Tobias Springenberg, Joschka Boedecker, and Wolfram Burgard. Deep reinforcement learning with successor features for navigation across similar environments. In 2017 IEEF/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 2371-2378. IEEE, 2017.
[70] Luisa Zintgraf. Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson. Varibad: A very good method for bayes-adaptive deep rl via meta- learning. In International Conference on Learning Representations, 2020. URL https: hik
/ //openreview
14

---

A Convergence Analysis
To gain deeper understanding why the rel-LLarning converges to maximum entropy policy, consider in this section a simplified dynamic programming variant in Algorithm 1. Note that the wo--Lerrnng estimates the SR for finite CMP for finite horizon length h. Consequently, the trajectory-action conditioned SR a (T:T, a) and exploration policy π can be stored in an exponentially large but finite look-up table. Furthermore, with every transition an additional state is appended to the trajectory T:r, meaning the agent cannot loop back to the same trajectory. Using these two properties, we state a dynamic programming variant of mě-Learning Algorithm and then prove its convergence to policy that maximizes the entropy term H (T)) + x0 (T:2, a)) at every time step.
Algorithm mpj-Learnnng: Dynamic Programming Framework
1: for all The a do
2: o6' (Tahe: a) <- Csa.
3: end for
4: for /. h, ...; do
5:
for all Tat do
6: (T. f- arg max, H (nT(T:-1) + + (T,,)))
7: 26" (T=-11 a) t c + (t)xb (Ta ((T:))
8: end for
9: end for
return such that (T) arg max, H(n(T:-1) + (p(
The convergence proof uses the following property of the predecessor trace 17 and SR "h"h Consider trajectory which selects action ar time step then
T
h Σ
-T:r-11 + "5 (Trr, or)
=
et)e., + E
(t)es,
Trr, ar
(by Eq. 5)
(1:r-11)
(Tirsar)
T-1
Σ 71)).. + +Err +Err-
(TT)e +
Σ (()es, TTT
(13)
1=++1
(t)e...
Errano
(t)es, T2
(14)
t=1
I=
(TT) Big- (+b (T.TI1, (TTTII (FT++)))TT
(15)
Using this identity, prove the convergence of Algorithm 1. Proposition 1. The policy x² returned by Algorithm where < h,
such that for every t-step trajectory T.
π (Tx) E arg max H (T((T.11) + t0" (Ta)))
(16)
Proof. The proof proceeds by induction on the length of an h-step trajectory, starting with length of h and iterating to length of one.
Induction hypothesis: We define sub- sequencee optimal policy n, such that for every k-step trajectory prefix T.A. and / < k < h,
Fe arg max (7((.x-1) + x0 (T.R, n (T.))))
(17)
The exploration policy mi is the optimal after executing the first steps of an h-step trajectory т. The goal is to prove that the induction hypothesis in line (17) holds for t t=
Base case: The base case for h holds trivially, because SR does not have a dependency on the policy for h-step trajectory. Therefore the policy n can output any action for trajectory sequence length h:
max H H(n((Th-1) + (T a (T.))) ((((Th-1)) (hh)es.)
(18)
15

---

Induction Step: Suppose the induction hypothesis in line (17) holds for some >> and xt is the
maximizer of
H (= + " (TAR, ne (T=)))) where S S h. For time step - 1, we have that for some action a,
(19)
(T + 3 (Ta-1, H (7(T:=2) + 7tt 1)e,, + + E (Ta mel (Ta))s(((1 ((-1. al)
(20)
H (7((T-1) + E T (T. Te (TA))
(21)
HE (T:TT11) + " (Te, Te (s-))]s)-1,a])
(22)
We note that the term inside the expectation already maximized by क, (by induction hypothesis). we now set 1 to be equal to for every 1-step or longer trajectory and set
(T-1(Ta-1)
arg max H (((T==-2) + ap (r=-1;
(23)
then for t - 1-15 s h
T- E arg max (( + (T.K,
(24)
This completes the proof.
B mo-Learning- Policy Gradient
Application of Q-Learning based approaches continuous action space is not easy because finding the greedy action at any time step can be slow to be practical with large, unconstrained function approximators and nontrivial action spaces. In this work, we take a similar approach to deterministic policy gradient [55] to Iearn exploratory policies. The objective remains the same which is to maximize the entropy of state visitation distribution. However, it is challenging to estimate the gradient where the objective is based on the entropy term. Previous works have either used alternate optimization [47, 31] or similar objective functions [18]. The challenge is because of the expectation inside the logarithm in Equation 2. [31, 47] addressed this intractability by first estimating the visited state distribution and then using this estimate to optimize the entropy-bard based objective. Unfortunately, such alternating approaches are often are prone to instability and slow convergence [18]. In this work, we take an alternative direction and learn network to directly estimate the visited state distribution. The combination of predecessor trace and successor representation sbt can be leveraged to estimate the state visitation distribution which is obtained using:
(TTT-1) (TT aT) Σ et),.. + Err+in
Σ (t)
T:T aT
(by Eq. 5)
(F(r-1)
(25)
The SR vector can be learned with gradient based optimization and provides the estimate of state visitation distribution for a given policy π and trajectory. The policy can utilize this estimate to learn optimal behaviors for efficient exploration in the environment.
To learn optimal behaviors for continuous action spaces, rpl-Learning uses actor-critic architecture comprising of a deterministic actor (T) that provides the action and critic to estimate the utility function. Here, both the actor and critic networks are Markkoooo and depend on the entire history of visited states. The goal of the critic network is to approximate the Q-function for a given trajectory and given action a E A. For given trajectory 7:r, critic computes this by combining the predecessor representation and the SR vector. The predecessor representation is fixed for a given history, implying that the critic only needs approximate the SR aba (T, a). To summarize, the critic estimates the Q O-function as shown below:
Qo (T.T, ar) H (7(TT-11 + (b((TTT ur))
(26)
To update the critic network, we update the SR approximator network using temporal-difffrence error. The target for the SR is obtained using the action coming from the current policy dr41 nn (7:T+1). and is given by
Cur + +T + (10(T..=1.0Tmm)
(27)
16

---

The SR network is updated with gradient- gradient-based learning to optimize the Mean-Square Error between the predicted SR and the target, and the loss function S is given by
Lsa = ( ar) (TTT 1-11)1112
(by Eq. 10)
Given an estimate of the SR for the current policy, we need a mechanism to update the actor network to maximize the objective. Deterministic policy gradient algorithm [55] provided a way of learning optimal policies with a deterministic actor. In this work, we formulate the gradient for the actor parameters using similar mechanism with the goal maximize the entropy-based utility function. Proposition 2 presents derivation of the gradients for the actor network parameters obtained by applying the chain rule on the Shannon-entroop based Q-function.
Proposition 2. Assuming the CMP satisfies [55, conditions A.1] (all functions are continuous and differentiable across all parameters) and for a j-parameterized policy function Tu the gradient with respect to of the maximum entropy objective
(TT) = Erppl (nnmpp(((((TT111))) + (T,
V [Fp) Eruup Σ
2 (T) (T. (=)
where 2; =- -log((((.-.))) + (TT - 1, H is the Shannon-Entropy function over the representation vectors, and the expectation over trajectories computed with respect to some trajectory visitation distribution p.
Proof. We begin by rewriting the Shannon Entropy here for a T Steep trajectory as
H H(m(Tr-1) + (T..r = Σ (m)(ar-1)s + (bT,,, ar)) (o + ( ar).,
(28)
where ar = (TTT)
To simplify the notations, will use 77 = and th; = (T.rr, ar); to represent the ith term of the predecessor and successor representation vectors. Now taking the gradient with respect to the actor parameters μ gives:
V H(, + +;) = V Σ (n: + +)) log(n: + +b))
(29)
1m + v.) log(n: + +b)
(30)
Σ Dog(n: + 1b) Vr (1: + +b;) + (m + V.), log(n: + +b))
(31)
Σ llogín + +b. b + Vn
(32)
Σ log(n, + +.) + 1| Rb
(33)
Now, using the chain rule on the ith feature in SR, we obtain
V Vub. V (TTz(TTT (ar(
(34)
By substitution
V +.)
log(n: +b)) + Vat.
(35)
Therefore, the gradient of the overall objective is
V (T)()T = Er~pl (((T..)()))))))))) + (TT,TT(T))
(36)
E
Σ log(n: + +.) Varka,
(37)
This completes the proof.
17

---

Algorithm 2 myū- -ea-nnen::::: Finite Action Space Framework
1: Initialize SR network with parameters 0 and the replay buffer B = 0
2: Denote the predecessor feature with 7, discount function with 7, and episode length with h
3: while Training do
4: Collect Teap = {s1, a1...,5h, using current policy Th and add it to replay buffer B=B L Teap
5: for each training step do
6:
Sample batch of t = ($1, .. -00-1,33) 31) ~ B of sequence length E (2, Compute a'= arg m (m (T(
7:
8:
Compute target y = e + (4)
9: Update SR network by performing gradient step on |yy (0((T--,0(--))
10: end for
11: end while
In Proposition 2, we derive the gradient of the actor parameters for the maximum state entropy exploration objective. Taking inspiration from algorithms [35, 17, 19] that extend Deterministic Policy Gradient (DPG) to make the optimization process stable when scaling to larger state and action space, we base our implementation to be similar to the TD3 [17] algorithm. In Appendix C, we outline the learning procedure to learn using the policy gradient derived in Proposition 2. Furthermore, we also discuss how the proposed algorithm handles continuous state spaces.
C Neural Network Architecture and Implementation
An implementation of the Lei-Lennning algorithm together with instructions for reproducing the experiments presented in this paper can be found htttps://gitii httb//tttuuu... cwm/ jrnavkj /99t/Et Psi_ Dei_Learning.
vul-Learning approximates the SR with parameterized function the to learn an exploration policy and predict the state visitation distribution. Because the SR is conditioned on a trajectory T of variable length, implement the function the with Recurrent Neural Network (RNN) architecture, as outlined in Figure In this architecture, the states in a trajectory T,T are first fed through a encoder network (E) comprising of Multi-Layer Perceptron (MLP) layers. Subsequently, the output of the Multi-Layer Perceptron (MLP) is fed through an Recurrent Neural Network (RNN) (denoted with F) architecture to compress the state sequence into real-valued feature vector. Since, RNN known to suffer from vanishing gradients [7], we implement the RNN with a Gated Recurrent Unit (GRU) [10]. Leveraging recurrent networks to learn the SR has been explored previously in [4, 8). Finally, the recurrent state obtained from the RNN is concatenated with the representation of the current state and is passed through the the decoder (D) with MLP layers predict an SR vector for given action. In the following paragraphs, we elaborate on how the proposed architecture was used to train the agent for finite and infinite action spaces.
Finite Action Space Variant For the finite action space variant, the decoder outputs a SR vector for each action a E A. This is similar to the prior method that learns Successor Features (SF) for discrete action spaces [33, 3]. Algorithm 2 describes the learning procedure for training mpj-Learning to get exploratory policies.
Infinite Action Space Variant For infinite action space variant, the hidden state from the recurrent network is passed through a deterministic actor network which comprises of MI.P layers. The policy network (actor) is conditioned on the hidden states because in npi-Learning the policy a function of trajectories and not individual states. The hidden state from the recurrent network is concatenated with the action to predict the SR vector. The estimated SR vector is used to calculate the visitation distribution over one-hot embeddings of states and these SR predictions are then used to computed loss objective for optimization. For the Reacher and Pusher tasks, we manually sub-select which dimensions of the state space are one-hot encoded. In these cases, nui-Lerning learns an exploration policy that maximizes the entropy of visitation distribution across these sub-selected dimensions only. This approach to sub-selecting state dimensions is similar to prior work on maximum state entropy exploration [23, 43]. this work, the agent is trained using similar techniques as the TD3 agent [17]. The agent keeps single encoder and recurrent network to encode the history of
18

---

Algorithm 3 ryp-L -earnnen:::::: Infinite Action Space Framework
1: Initialize SR network with parameters 0,, 02, policy parameters μ and the replay buffer B = 0
2: Set target parameters equal to the main parameters: 0sarg,1 = 01, Otarg, = 02, and jttrgg <- /
3: Denote the predecessor feature with 7), discount function with 7, and episode length with h
4: while Training do
5: Collect Teap {51, d1, d1,.., .1, using target policy Tptara and add replay buffer B=B U Temp
6: for each training step j do
7:
Sample batch of r ($1, -,, ~ B of sequence length (2, Compute target actions a' = clip( (T:)) + clpp(c, -c, c), aLow: (High); ) c < 1V
8:
9:
Compute i=arg (1.)) (1) [.--1) L0, (T=-1,u"))
Compute target y=e,, + (1) bo (Tu-1, a')
11:
Update the SR networks by performing gradient steps on 1=
l 11y-4e, 1o,,,b,.TT--1 (T=-1I j % volicy_update == 0 then
12:
13:
Perform update step for policy by computing gradients using
>; Va th, (Ta,a) a=n(ra) V, Tu (Ta), where 2 log(n(ra); v0. (Ta, T (Ta)):) +1
Update target networks with
Orarg f- prrgg, + (1 p1-p)
i= 1,2
Ptarg Piltarg + (1 p)p
15: end if
16: end for
17:
end while
observed states. The encoded states passed through two decoder networks to predict the SR vectors, which are used to represent the two critic networks. The target for SR computed using the vector that leads to smaller value of the two utility functions. There is single actor network that specifies the action from the hidden state. In addition, myp-Learnigg-maintain a target network for all the components-encodde TD3 algorithm, a clipped noise added to each dimension of the action from the target network. Moreover, we also use delayed actor updates where the actor network is updated less frequently than the SR networks. Lastly, the gradients from the actor are not passed through the encoder and the recurrent networks. The procedure for training this variant provided in Algorithm 3.
recurrent, crities, and actor networks. Furthermore, similar the
H (T )
D
F
F
E
E
E
SO
St-1
St
Figure 6: Network architecture learn the SR. The states are firstly passed through an encoder (E), followed by feeding the encoded states through RNN (GRU in our case) (F). This compresses the history visited states, and the obtained hidden state concatenated with the encoded state to predict the SR vector for an action using a decoder network (D).
19

---

D Limitations
In this work, we developed an algorithm learn exploratory policies at convergence that can explore the state space efficiently within a finite-length trajectory. Such policies can benefit generalization in different applications like Meta-RL and episodic exploration. Maximum state entropy exploration is a potential direction for learning such policies. However, prior works are not very efficient as they either learn a Markovian policy, optimize for the state coverage over multiple long trajectories, or learn a mixture of stochastic policies. Due to these shortcomings, they are not widely used for solving tasks in RL. To address these concerns. we introduce 77s-Learnnnandd demonstrate that the proposed algorithm can learn to efficiently explore the state space within finite length trajectory. Lerning achieves this by combining predecessor and successor representation to estimate the state-visitation distribution and utilizing this to optimize the entropy -hased objective. [43] theoretically showed that learning such policies that achieve zero-regret is NP-Hard and we develop a practical algorithm to solve such tasks. We hope that the proposed method bridges the gap of leveraging policies learned using maximum state entropy exploration for more complex tasks in RL. As with any new approach, there are certain limitations:
Scaling to high-dimensional inputs: Learning to explore more complex tasks with high- dimensional input spaces would require using a better representation learning method and a mechanism to estimate successor and predecessor representations. For representation learning, existing methods that use auxiliary losses, inverse/forward dynamics, or random network-based based features can be used. The more challenging task is learning the SR and future works can explore leveraging methods like Successor Measures [62] or ProtoVat Val- ueNetworks [15].
Environments with changing dynamics: The learned SR depends on the environment dynam- ics and the policy, and we learn SR for a fixed environment in this work. However, many real-world tasks require exploration in an environment with changing dynamics (procedural environments [24, 67].. A potential direction is learning universal successor representation approximators [8] where the successor representations are conditioned on context that defines the environment and we leave this for future research.
Architectural priors for estimating SRs: The successor representations use an RNN which is known to suffer from vanishing gradient problems. Many real-world tasks require agents to retain information over multiple timesteps. Future research can explore having better architectural priors like Transformers S4 that have better memory and are known to work well on complex tasks.
Estimating predecessor representation: In this work, we computed the predecessor repre- sentation as the summation of the prior state representations. However, recent methods like Expected Eligibility Traces [64] show better sample efficiency and we leave leveraging such methods for future research.
Computing entropy instead of state visitation distribution: While predicting future state visitations may seem harder than needed for entropy prediction, it is important to note that optimal decision depends on which states are visited multiple time steps into the future. is possible that there exist more efficient algorithms for predicting this entropy, but to our knowledge such algorithms do not appear the published literature, and rpei- is the first of this kind. Another challenge with estimating entropy is that the estimator needs to adapt to the changing policy during training. In the proposed algorithm, this is mitigated both the entropy and policy directly depend on the estimated SR vector requiring no additional updates to estimate entropy given the policy. However, future work would involve discovering other more efficient methods for estimating the entropy induced by the future state visitations.
Comparison to Forward- Backward Representation [63]: The forward-Backwall represen- tations [62. 63] capture similar state visitation statistics as the predecessor and successor representation used by nel-Learning Mathematically, the forward-backwart (FB) rep- resentation factorizes the Q-function in an RL setting in a very different way than the rpu-Learning algorithm. The FB method also focuses on a reward-maximization setting instead of exploration and are only conditioned on states whereas the 1 algorithm conditions these representations on trajectories. During training, the focus of FB learning is representation learning using offline dataset where it is assumed that the agent does
20

---

not have to explore the environment. The learned FB representations are then used to solve multiple different tasks using the same representations, assuming that reward parameteriza- tion is known. However, the 7jj--Learning algorithm learns exploratory policies that could used to initially explore an unknown task determine this reward parameterization. We believe that the 7pp-Learnnng algorithm complements the FB method and integrating the two systems into a cohesive RL agent is an interesting avenue for future research.
E
Discount Function
Q =1.0
a =0.9
2.7
2.6
2.5
2.4
T (1)
T (2)
T (3)
Figure 7: Illustration of the values of the entropy with different value of a hyperparameter in the proposed y-function for the trajectories introduced Figure 1.
In this work, we have used denendepnddntt y--function. Using the gridworld example described in Figure
present how the choice of y-function affects the entropy term in the objective. Suppose there are three trajectories followed by the given trace T:r, where we denote the i-th trajectory with (() Here, Figure 1(b) shows an optimal trajectory (7(1) which combined with trace covers each cell of the grid with 15 steps. Figure I(c) presents a suboptimal trajectory (7(2) where the agent takes the right action from the current state and visits a previously observed state in the last step. Figure (d) shows another sub-optimal trajectory (3) which takes the right action in the current state but visits the new state twice because goes the top right corner the grid.
For the intermediate step T, we define the discount factor for the predecessor representation for the trace as (t) =
r- z where is scalar between (0, 1]. and Z = DT + D/ is the normalization factor. The 7-function for the successor representation is denoted using 7(1) = a'-T The proposed y-ffnction for both the representations is similar discounting used standard RL literature [13, 59]. Upon comparing the entropy for given trajectories with a 0.9, 1.0, we observe in Figure 7 that (I)) being the optimal trajectory attains higher entropy when compared with ((2) and -(3), The other sub-optimal trajectories (2) and (3) achieve same entropy when a is set to 1.0. However, for
0.9, the discount function emphasizes which states are visited earlier in the trajectory and assigns the lowest score to the trajectory (33) because this trajectory revisits states earlier in the sequence than the other options 7(2) and -(1) This example illustrates how the y f-functionn can be used to trade off near-term vs. long-term exploration behavior, Depending on the setting, the agent can be encouraged to avoid re-visiting states either only in the short-term or the long-term, similar how discounting encourages maximizing short-term over long-term rewards in algorithms like Q-learning.
Environments
For finite action space variant, experimented with ChainMDP, RiverSwim, 5 x Grid-world, TwoRooms and FourRooms environments, which have finite action and state space, respectively. For infinite action space variant, experiment with Reacher and Pusher environments where want
21

---

SP
(b)
(c)
Figure 8: (a) RiverSwim [58], (b) TwoRooms, and (c) FourRooms environments, respectively. The yellow block denote the initial state of the agent in each episode. The brick red regions represent the walls in the environment. When taking an action that collides with the walls, the chosen action does not change the state of the agent.
(a)
(b)
Figure 9: (a) Reacher and (b) Pusher environments for experiments with infinite action space.
the agent to move its fingertip to different locations in the environment. The environments used in this work are further described below:
ChainMDP is an environment where the agent can take only move in two directions- left right. In this work, we experiment with both deterministic and stochastic version of ChainMDP environments. The stochastic ChainMDP similar to RiverSwim environment [58] (Figure 8(a)).
ChainMDP:
GridWorld: In the Gridworld environment (shown in Figure 1), the agent take 4 actions to move in any of the directions. In this work, we experiment with the gridworld of dimensions 5 x 5. The agent always start in the top left corner of the grid. For the gridworld, there are multiple possible optimal trajectories, and the number of such trajectories increases explonentially with size of grid.
The proposed TwoRooms environment is gridworld with some walls. As shown in Figure 8(b), the agent starts at the center wall between the two rooms and has to first navigate in one of the rooms, visit the starting state and then move to the other room. This makes the task challenging as the agents requires to track the trace because when the agents reaches initial state after exploring room, the information of which room was visited should aid in going the other room.
TwoRooms:
The FourRooms environment (depicted Figure 8(c) has four rooms connected which connected by open shots between the walls. This task is even more challenging as the agents while navigating need to first explore the current room followed by efficiently going across different rooms.
FourRooms:
The Reacher environment (shown in Figure 9a)) a continuous control environment having two-jointed robotic arm with continuous state and action spaces. The action space denotes the torques applied to the hinges. The state denotes the position, angles and angular velocities of the arms. The agent is tasked to maximize the entropy over the position of the fingertip.
Reacher:
22

---

The Pusher environment (shown in Figure 9()) is a continuous control environment having a multiple-jointed robotic arm with continuous state and action spaces. The action space denotes the torques applied to the hinges. The state denotes the position, angles and angular velocities of the arms/hinges. Similar to the Reacher environment, the agent tasked maximize the entropy over the position of the fingertip. However, this task is harder to solve because having multiple joints leads to a larger action and state space making it a more challenging control problem.
Pusher:
For training and evaluation, we have used different parameters specific to each of the environment. For training, the parameters are the length an episode and the number of episodes used for training. The number of environment steps can be obtained by multiplying these 2 parameters. For evaluation of an agent, we use different episode length for the three metrics defined measure the performance of agents in section 5.
Name
ChainMDP
RiverSwim
Gridworld
TwoRooms
FourRooms
Training Purameters
Length of trajectory from enviromment Number of episodes
50
50
100
200
1000
1000
1000
1000
2500
Evaluation Purametert
Horizon à for Entropy metric Horizon h for State Coverage metric Horizon measure Episade Length
50
50
100
200
20
50
50
100
200
Table 1: Defines the parameters of the environments with discrete actions during training and evaluation, respectively.
Name
Rencher
Pusher
Training Porameters
Length of trajectory from environment
100
200
Numher of episodes
1000
1000
Evaluation
Horizon for Entrogy metric Horizon for State Coverage metric
200
200
Table 2: Defines the parameters of the environments with continuous actions during training and evaluation, respectively.
G Hyper Parameters
In this section, we describe the hyperparameters used for training the proposed method rpé-Learning. Table 3 and Table 4 presents the list of hyperparameters for the discrete and continuous control environments, respectively. All models were trained on a single NVIDIA V100 GPU with GB memory. The implementation of the proposed method was done using the RLHive [46] library.
H Meta-RL
In this work, we demonstrated how mu-Learning can learn optimal policies that can maximize the entropy of state visitation distribution. Such policies are useful for many subareas of RL where during evaluation the task adapt to new reward functions with minimal interactions with the environment. A challenging subproblem in such tasks is to infer the reward function. This is especially harder when the reward is sparse. Some recent works have explored adding exploratory behaviors for initial interactions with the environment to allow agent to infer the reward function. VariBAD [70] algorithm learns optimal policies that can explore during evaluation to speed up adaptation for Meta-R RL tasks. VariBAD maintains a belief over the state space to explore in the environment and upon discovering the reward function adapts to the illustrate the exploratory capabilities n Leanning, we compare with VariBAD as baseline in this section.
23

---

Name
Value
Batch Size
32
Sequence Length
10/ 20/ /0//0////00000000//////////////0 / 50/ 100
a for y-function
0,95
Encoder layers
1
Encoder output dimensions
64 / 64 128 / 128 256
Encoder activation
Leaky [68]
Hidden state of GRU
64 / 64 128 / 128 256
Hidden layer dimension for SR decoder
32 32 / 64 / 64 128
Decoder activation
None
Optimizer
Adam [29] 3e-4 200000
Learning rate
Capacity of replay buffer
Table 3: Hyper parameters used for training mii-Lernning When parameters are separated by I.J.J., means the corresponding hyperparameters for ChainMDP, RiverSwim, Gridworld, TwoRooms and FourRooms environments, respectively. When tuning the agent for task, we recommend searching over a E {0.9, 0.95, 0.98, 0.99], and hidden state dimension of GRU and encoder output dimensions in {64, 128, 256, 512]. For the replay buffer, we have used the replay buffer implemented in DreamerV2 [20], which for an episode samples a chunk of a given length.
Name
Value
Batch Size
256
Sequence Length a for o-function
100
0.95
Encoder layers
2
Encoder output dimensions
256
Encoder activation
Leaky [68]
Hidden state of GRU
256
Hidden layer dimension for SR decoder
256
Decoder activation
None
Optimizer
Adam [29]
Learning rate
3e-4
Capacity of replay buffer
200000
Polyak constant
0.005
Grad Clip
5.0
Action noise
0.1
Target noise
0.2
Table 4: Hyper parameters used for training nee-LLarning on continuous state space environments. When tuning the agent for task, recommend searching over E {0.9, 0.95, 0.98, 0.99), and hidden state dimension of GRU and encoder output dimensions in {64, 128, 256, 512]. For the replay buffer, we have used the replay buffer implemented in DreamerV2 [20], which for an episode samples a chunk of given length.
The implementation of VariBAD provided by the authors used to conduct this experiment. The baseline was trained for 10 million environment steps the gridworld using the setup described in the paper. Two metrics are employed to compare the agents:
State Coverage computes the fraction of the state space covered by the agent.
Goal Search Time computes the environment steps taken locate the sparse reward goal state. This evaluates the ability of the agent at quickly finding the reward which is essential for swift adaptation novel tasks.
The two metrics evaluate the agents average time taken to find the reward function and the average search completion time for covering the grid. The VariBAD [70] algorithm considered sparse reward task where a random location is sampled after each episode the goal state and is assigned a high

---

reward. To compute the Goal Search Time metric, we sample goal state randomly and record the steps taken locate the target state. For evaluation, the metric is averaged over 16 sampled goal state for each seed. Figure 4(c) presents the comparison of VariBAD and <pé-LLerning across 5 seeds. The proposed method reainnn achieves outperforms VariBAD on both metrics while only being trained for 100K environment steps. This demonstrate the efficacy of myj-Learning at exploring environment that involves inferring the reward function during evaluation.
both metrics mo-LLerrnng can be combined with adaptation policy, where the proposed method can explore to find the reward and the adaptation policy is trained to adapt quickly to the reward function, and we leave this for future work.
believe
I
Ablation Studies
In this section, we present ablations studies to understand the gains of the proposed method syú- Learning.
1.1 MaxEnt with recurrent network
RiverSwim
TwoRooms
FourRooms
4.0
1.50
M
Entropy
1.25
1.00
0.75
0.50
200
400
600
80D
2000
200
400
600
800
1000
250
500
750
1000
1250
1.0
1.0
1.0
Covereat
0.8
0.8
0.8
0.0g
200
400
600
800
2000
0.0g
200
400
600
800
1000
0.0g
250
500
750
1000
1250
Search Completion Time
400
800
800
200
600
600
200
400
400
%
200
400
800
80D
2000
%
200
400
600
800
1000
%
250
500
750
1000
1250
Episades
Episades
Episades
MaxEnt
MaxEnt-GRU
ng Learning
Figure 10: Comparison of the baseline MaxEnt when trained with a recurrent network.
We conduct an experiment with modification the baseline MaxEnt [23] where agent observed the history of visited states. This is done to evaluate if the improvements are coming from having a recurrent policy. To this end, the conditiond policy in MaxEnt is replaced with a recurrent policy where the GRU [10] encodes the states observed in the trajectory. The parameters of the recurrent policy is optimized using the loss function described MaxEnt [23]. Figure presents the results of MaxEnt with a recurrent policy (named MaxEnt-GRRU -RUnt where gains are observed by having recurrent policy and the proposed objective function used train Lpa-Leanning crucial for learning optimal behaviors.
25

---

5x5 GridWorld
TwoRooms
FourRooms
3.2
3.2
3.6
3.0
Entropy
3.4
2.8
2.8
3.2
2.6
2.6
+
10
25
1
2
5
10
25
1
2
5
10
25
1.0
+
State Coverage
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.0
10
25
1
2
5
10
25
5
10
25
Number of Trajectories
Number of Trajectories
Number of Trajectories
MaxEnt
ny-Learning
Figure 11: Comparison of ret-Learning with baseline MaxFnt when metries are computed using multiple trajectories. MaxEnt-X denotes the evaluation with X trajectories.
1.2 Comparison across multiple trajectories
Contemporary methods on Maximum State Entropy Exploration [23, 42] were evaluated by averaging the state visitation distribution over multiple trajectories. In this work, we demonstrate that yy-- Learning can achieve optimal behaviors over single trajectory of finite length. In this study, we also explore comparison of the baseline MaxEnt when evaluated over multiple trajectories. For this evaluation, we sample a batch of trajectories and then average the state visitation distribution of trajectories. The metrics are then computed using this averaged visited state distribution. In Figure 11, we compare the Entropy and State Coverage over this averaged distribution. MaxEnt-X denotes the metric of MaxEnt after sampling X trajectories during evaluation. The proposed method mui-eeaningwas evaluated using a single trajectory. We do not report metrics of yye-Leanningaeros multiple trajectories we observed that the gains do not vanish with an increasing number of trajectories. The metrics for the MaxEnt algorithm improve with the increasing number trajectories used for evaluation. With 10 more trajectories, the baseline achieves optimal State Coverage. However, mei-Learnig achieves full coverage with a single trajectory demonstrating the efficiency of the exploration policies learned using the proposed method. The baseline MaxEnt show similar behaviors by improving on the Entropy metric with more trajectories used for evaluation, whereas 77ch- Learning still outperforms the baseline when evaluated using single trajectory. This demonstrates that the proposed method explores the state-space with near-equal state visitations to maximize the entropy while having optimal state coverage in single trajectory.
1.3 Effect of the a parameter
We also study the effect the hyper-parameter a of the 7-function (discussed in Appendix E). We note that can be selected using the same method used select the discount factor the standard RL. We conducted experiments with a=(0.8,0.9) 1.0.8,.9900.9....... 0.9.0.95,0099) across three environments- RiverSwim, TwoRooms, and FourRooms (Figure 12). On the RiverSwim environment, all methods converged with similar values across all metrics. On the TwoRooms environments, agents with a=(0.8, 0.99) were not performing well across the three metrics. Moreover, the convergence was slower for agent with a 0.9 when compared with agent trained with 0.95. Our intuition behind this is that when a is smaller, the memory of the visited states in predecessor representation (1)) reduces leading to re-visitation of observed states. Whereas when is large, then the agent does similarly discount a future state any point in the trajectory. Lastly, on the FourRooms environment, the results are similar to the TwoRooms environment but with more pronounced differences in metrics for different
26

---

RiverSwim
TwoRooms
FourRooms
3
3
1.5
Entropy
2
1.0
W ga
1
0.5
0
200
1000
1.0
1.0
1.0
State Coverage
0.8
0.8
0.8
ww
0.6
0.6
WW
0.6
0.4
0.4
MVW
0.4
MMm Mmmm
0.2
0.2
0.2
0.0
200
400
600
800
1000
0.0
200
400
600
800
1000
0.0
200
400
600
800
1000
Search Completion Time
1000
1000
25000
800
800
2000
600
600
1500
400
400
1000
200
200
500
0
200
400
600
800
1000
0
200
400
600
800
1000
0
200
400
600
800
1000
Episodes
Episodes
Episodes
0=0.8
0=0.9
0.95
00999
Figure 12: Evaluation with different value of a hyperparameter in the proposed y funnctio
values a. This because FourRooms environment is harder to solve than TwoRooms environments. Notably, the Search Completion Time metric diverges for all values of 0.95, which shows that 0.95 leads to optimal behavior for our task. For new tasks, we believe a can be tuned similarly the discount factor used in standard RL.
1.4 SR conditioned on state
In this section, we validate if conditioning on the history of visited states important for learning optimal SR vectors. We consider variant of ne-LLerning where the SR is only conditioned on the current state. However, the objective proposed in Equation which uses predecessor representation to compute the entropy is used for learning. We conduct experiments on continuous control tasks where we observe that conditioning on the entire trajectory sequence important for learning optimal SR vectors (Figure 13).
1.5 Visualization of trajectories
The maneuvers taken by the learned r/f-Learning agent were also visualised. For the Reacher environment, the agent was first covering the faraway states followed by covering the nearby states to the central position. Similar behaviors were observed for the Pusher environment, where the agent was moving the fingertip to different locations on the table top and tried visiting reachable locations the table.
J Comparison on Sparse Mountain Car
In this work, we showed how the proposed method ryj-Learning can learn policies to efficiently explore in environment. To present the applicability of the proposed method to other settings,
27

---

Reacher
Pusher
3
Entropy
2
200
400
600
800
1000
200
400
600
800
1000
1.0
1.0
State Coverage
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0
200
400
600
800
1000
0.0
200
400
600
800
1000
Episodes
Episodes
ny (State based SR)
ny-Learning
Figure 13: Comparison with proposed variant where the SR is conditioned the state only denoted as rellLLernnng (State based SR). We see that conditioning on the entire trajectory is important for learning SR vectors to optimize the objective.
T=0
T=5
T=10
T=15
T=20
T=25
T=30
T=35
T=40
Figure 14: Rolled out trajectories using the learned mo--Lennnng agent on the Reacher (top row) and Pusher (bottom row) environments at different time steps, respectively.
we conduct an experiment tasks with sparse rewards. We consider the Sparse MountainCar environment where the agent receives a positive reward after reaching the goal position after which the episode terminates and the agent receives reward in other states. We chose this environment because reward is sparse, and hard for the agent to discover reward function as the agent needs to plan to explore the top of the hill. For the baselines, we compare with random agent, TD3 [17]. TD3 combined with count- based bonus [6] as an intrinsic reward (TD3-Count), and TD3 combined with first occupancy bonus [40] as intrinsic reward (TD3-First).
We also propose a variant of our method learn with extrinsic rewards. We modified the TD3 algorithm and call the proposed variant TD3-moý-Lerrnng In this variant, we propose to learn 2 critics- one to estimate the SR mentioned in 4 (Q and the other to estimate the returns obtained using extrinsic rewards (Q The critic based on extrinsic rewards Qezt is conditioned on the current state learned using the update rule defined TD3 [17]. Notably, Qeapl and Qezt are conditioned on the trajectory of prior visited states and current state, respectively. To learn the actor, the gradients are obtained using the overall Q-function which defined as the linear sum of both Q- v-luusss based extrinsic rewards and entropy-based term: Q Qent + BQeeppl where & denotes
28

---

Algorithm 4 my-- :pi-Learnnng: TDD-mij-Larrning
1: Initialize SR network with parameters 01, 02. Q network with parameters for Q-function with extrinsic rewards Φ1. 22 policy parameters μ and the replay buffer = O
2: Set target parameters equal to the main parameters: 0zarg,1 01, 0zarg,2 02, Qtarg.1 Ø1, @targ.2 = Φ2, and lttrg <- ll
3: Denote the predecessor feature with n, discount function with 7, and episode length with h
4: while Training do
5: Collect Texp - {51, 0 Tl, S using Tptaro and add replay buffer B-B U Teap
6: for each training step j do
7:
Sample batch of r = ($1, al 1, 11-1; st) of sequence length I (2,.., Compute target actions a' = clip T Hearg (T:I) + clip(e, -c, c), aLow: (High), c NN 1)
8:
9:
Compute i=arg (1.2) (( [.1-1) 10 (T=-11a0))
10:
Compute target for SR
ya=es; + (1) t (T
Update the SR networks by performing gradient steps on i = 1,2
Vaa $0,, (Ta-1,0-1)11 1111)
Compute target for Quaat
y + Next min Qoet drara (st, a')
Update the Q networks by performing gradient steps on
yya (
i i= 1,2
14:
j % policy_uppee _u__atedeee == then
15:
Perform update step for policy by computing gradients using
>: 2 Va the (Ta:a) (==((r)) V (T()T)) V Qs (1-1
where 2; -log(n(Ta)s t0, (Ta, Tu (Ta))) +1
16:
Update target networks with
θ ftarg. f praagg + (1 p)d, Ptarg t- Plitag + p)j
i i= 1,2
17:
end if
18: end for
19:
end while
the trade-ofi off between the two Q-functions. We have added a pseudo-code to describe the proposed algorithm in Algorithm
Figure 5 presents the results on the Sparse Mountain Car environment. We compare two metrics- Return and Episode Length denoting the steps taken reach the goal state across 5 seeds. The Average Steps metric highlights if the agent learns to solve the task with minimal interactions. We plot the mean and 95% confidence interval shading. The proposed method outperforms TD3 and variants with count-based and first occupancy based bonuses. Through our experiment on Sparse MountainCar, we demonstrate that the proposed method can improve efficiency in standard RL tasks, especially in sparse reward environments. We leave it for future work to leverage the proposed extension in POMDP setting with more complex input spaces.
29


Reviews:
[{"review_id": "xRSMViMEVk", "reviewer": "Reviewer_RPnY", "summary": "This paper proposes a novel exploration algorithm in RL by combining the successor representation with the predecessor representation and maximising episode-level entropy of state visitation. The proposed approach demonstrates improvement over the MaxEnt baseline on simple Gridworld and continuous control environments.", "questions": "Please refer to the comments listed in the Weaknesses section.", "limitations": "The authors have discussed general high-level ethical concerns with this line of work, but the limitations of the proposed approach have not been discussed.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper presents a nice way to bridge the successor and predecessor representation to maximise entropy in the visitation of states in an episode.\n- The paper is clearly written and well motivated.", "weaknesses": "- In the experiments, the proposed approach is only compared with the MaxEnt baseline. While this is a good baseline to compare with since the objective is similar, the standard exploration baselines are missing: 1) epsilon-greedy exploration, 2) count-based intrinsic motivation approaches like UCB, 3) random action baseline, and optionally 4) auxiliary objectives for exploration, like curiosity-based learning. While I agree with the related work section that these works learn Markovian policies while the proposed work learns a policy conditioned on the full history, a couple of them should still have been included, to place this algorithm in the overall landscape of exploration algorithms.\n- Since the successor representation and the predecessor representation in this case both depend on the full history, it is not possible to disentangle the impact they have on exploration and the evaluation metrics as there is no baseline included in which the successor representation depends only on the current state.\n- A relevant paper that is missing from the related work section, and also from the baselines, is \"A First-Occupancy Representation for Reinforcement Learning\" by Moskovitz et al, which is another state representation that indicates the time of first access of a state by the agent and has been shown to be conducive to exploration.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and valuable feedback. We aim to address the concerns in the following:\n> In the experiments, the proposed approach is only compared with the MaxEnt baseline. \n\nWe thank the reviewer for pointing this out. We did an experiment with the sparse MountainCar environment (Figure 4 in Rebuttal PDF) and showed that the proposed method promotes exploration in sparse reward environments. We have described this experiment in more detail in the General Response section. Furthermore, we did not compare intrinsic curiosity and count-based methods on reward-free tasks as such methods do not learn exploratory policies at convergence. This is because the intrinsic curiosity or the count-based bonus becomes zero or uniform at convergence. This was also discussed in Section 2 in SMM [1], where they elaborate on the difference between such methods and the current method’s line of work. We agree with the reviewer that the exploration algorithm based on maximum state entropy exploration should be compared with the prior works on exploration and hope the MountainCar experiment presents the benefit of the proposed method. Lastly, we have also added MEPOL [2] which learns a Markovian policy and uses a non-parametric entropy estimator to learn optimal policies for continuous control tasks, and a random policy as additional baselines (Figure 3 in rebuttal PDF).\n\n> There is no baseline included in which the successor representation depends only on the current state.\n\nAs suggested by the reviewer, we conduct experiments on Reacher and Pusher environments where the successor representation is conditioned over the current state only. However, the predecessor representation is only used to compute the state visitation distribution which is necessary for the objective function. In Figure 3 of rebuttal PDF, we can observe that the modification does not perform well on both these tasks, and learning SR conditioned on the history of visited states is necessary for learning optimal behaviors. \n\n> A relevant paper that is missing from the related work section, and also from the baselines, is \"A First-Occupancy Representation for Reinforcement Learning\" \n\nWe thank the reviewer for pointing this out. We were unaware of this work and have added this paper to the related works section. Furthermore, in the experiment on Sparse MountainCar, we also used the First Occupancy-based intrinsic reward as the intrinsic bonus in each episode for comparison, where the proposed method was found to perform better. \n\n> The authors have discussed general high-level ethical concerns with this line of work, but the limitations of the proposed approach have not been discussed.\n\nIn this work, we focus on developing a method that can be optimized with maximum state entropy objective and learn to explore within a single episode of finite length. As with any new approach, there are certain limitations:\n1. *Scaling to high-dimensional inputs:* Learning to explore more complex tasks with high-dimensional input spaces would require using a better representation learning method and a mechanism to estimate successor and predecessor representations. For representation learning, existing methods that use auxiliary losses, inverse/forward dynamics, or random network-based features can be used. The more challenging task is learning the SR and future works can explore leveraging methods like Successor Measures[4] or ProtoValueNetworks[4].  \n2. *Environments with changing dynamics:* The learned SR depends on the environment dynamics and the policy, and we learn SR for a fixed environment in this work.  However, many real-world tasks require exploration in an environment with changing dynamics~(procedural environments [5]). A potential direction is learning universal successor representation approximators [6] where the successor representations are conditioned on a context that defines the environment and we leave this for future research.\n3. *Architectural priors for estimating SRs:*  The successor representations use an RNN which is known to suffer from vanishing gradient problems. Many real-world tasks require agents to retain information over multiple timesteps. Future research can explore having better architectural priors like Transformers or S4 that have better memory and are known to work well on complex tasks. \n4. *Estimating predecessor representation:* In this work, we computed the predecessor representation as the summation of the prior state representations. However, recent methods like Expected Eligibility Traces [7] show better sample efficiency and we leave leveraging such methods for future research.\n\n\nLastly, we have added these limitations to a separate section in the paper. We hope we addressed most of your questions, and hope you consider updating your score.\n\n#### References\n[1] Lee, et al., \"Efficient exploration via state marginal matching.\" arXiv preprint arXiv:1906.05274 (2019).\\\n[2] Mutti et al., \"Task-agnostic exploration via policy gradient of a non-parametric state entropy estimate.\" AAAI’21.\\\n[3] Touati et al., \"Learning one representation to optimize all rewards.\" NeurIPS’21.\\\n[4] Farebrother et al., \"Proto-value networks: Scaling representation learning with auxiliary tasks.\" ICLR’23.\\\n[5] Zha et al., \"Rank the episodes: A simple approach for exploration in procedurally-generated environments.\" ICLR’23.\\\n[6] Borsa et al. \"Universal successor features approximators.\" arXiv preprint arXiv:1812.07626 (2018).\\\n[7] van Hasselt et al., \"Expected eligibility traces.\" AAAI’21.\n"}, {"review_id": "MB3qrAsPat", "reviewer": "Reviewer_L5xE", "summary": "This paper proposes a new exploration method under maximum entropy RL settings. At each time step, the agent selects the action that maximises the expected entropy of the finite-length trajectory. The trajectory entropy is decomposed into two terms, based on variants of the predecessor representation and successor representation, respectively. The authors proposed separate training frameworks under discrete and continuous action spaces. The resulting agent is evaluated in grid worlds with different configurations. ", "questions": "See questions in Weaknesses.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The proposed decomposition of trajectory entropy objective is novel;\n- The authors provide comprehensive description of Q-learning and policy gradient training under discrete and continuous action spaces, respectively. \n- Empirical evaluations are comprehensive and coheres with the arguments in the paper;", "weaknesses": "- The predecessor representation part (for the computation of the entropy of past trajectory) seems unnecessary and does not contribute to action selection, could the authors elaborate on this point?\n- The evaluations in continuous control tasks is still within the grid world environment, could the authors evaluate the proposed agent in standard exploration-demanding continuous control tasks;", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and valuable feedback. We aim to address the concerns in the following:\n> The predecessor representation part (for the computation of the entropy of past trajectory) seems unnecessary and does not contribute to action selection, could the authors elaborate on this point?\n\nThe entropy is dependent on the state visitation distribution which is computed across the entire trajectory in the episode. At any time (T), the agent has access to the history of states and needs to take action to maximize the entropy of the state visitation distribution. Since the visited states till time T are known to the agent, they are used to compute the visitation distribution for the first T time steps resulting in the predecessor representation vector (Equation 5). To estimate the distribution of the future states, the agent predicts the expected visitation distribution of future states—the successor representation vector as defined in Equation 6. The predecessor representation is used to encode the visitation distribution of past states and the successor representation is used to predict the visitation distribution of future states (see our example in Figure 1). In Equation 7, we propose to aggregate them, which gives the expected state visitation distribution for the whole trajectory. The Q-function is defined as the entropy of this estimated state visitation distribution. Although the successor representation is conditioned on the previously visited states, we need predecessor representation to calculate this expected state visitation distribution and thus the state visitation entropy of a single trajectory, as stated in Equation 7. Since the agent selects an action based on the Q-function, the action selection is conditioned on the state visitation distribution which further depends on the predecessor representation. We have expanded on this in the revised version of the paper to explain the importance of predecessor representation in the action selection. \n\n> The evaluations in continuous control tasks is still within the grid world environment, could the authors evaluate the proposed agent in standard exploration-demanding continuous control tasks;\n\nThe experiments on continuous control tasks were conducted on the state space provided by the environment. The input to the recurrent architecture~(Figure 5 in Appendix) is the continuous 8-dimensional and 27-dimensional vector obtained from Reacher and Pusher environments, respectively. The predecessor and successor representation is computed over the discretized vector obtained using the (x, y) coordinates of the fingertip. To further show that the method can scale to harder continuous control tasks where we would want to compute the entropy over a larger state space, we conducted an experiment on HalfCheetah environment. Taking inspiration from ProtoValueNetworks [1] to avoid the curse of dimensionality while discretization, we discretize each dimension of the state space separately and compute the overall entropy by averaging the entropy across all dimensions. The successor and predecessor representations are computed on the 17-dimensional state space, where each part is discretized into 10 bins for our experiments. Also, the state coverage in evaluation metrics is computed as the average coverage across the discretized dimension. We report the results in Figure 2 in rebuttal PDF where the results are obtained across 5 seeds. We compare with MEPOL [2] which uses Markovian policy and uses kNN to estimate the entropy. $\\eta\\psi$-Learning was found to have better coverage and entropy over the discretized state space demonstrating that the proposed discretization can be leveraged to scale the proposed method to large state space. We leave it for future research to extend the method to explore POMDPs with more complex environments, including images and have added these discussions to the revised version of the paper. \n\nWe thank the reviewer for the feedback. We hope we addressed most of your questions, and hope you consider updating your score.\n\n#### References\n[1] Farebrother et al., \"Proto-value networks: Scaling representation learning with auxiliary tasks.\" ICLR’23\\\n[2] Mutti et al., \"Task-agnostic exploration via policy gradient of a non-parametric state entropy estimate.\" AAAI’21."}, {"review_id": "Tfd86tczRA", "reviewer": "Reviewer_gBvc", "summary": "This paper shows a combination of \"succesor\" and \"predecessor\" representations can be used to develop an efficient maximum entropy exploration policy.", "questions": "The authors should be able to easily address my releatively minor comments in the \"weaknesses\" section.\n\nMore broadly, I think the general usefulness of this approach will depend on how it can be applied beyond the maximum entropy exploration setting.\n\nUPDATE: the authors have addressed my comments.", "limitations": "In the Discussion, the authors discuss several ways to improve and extend their algorithm.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Overall, the paper is clearly written and makes a useful contribution to the exploration literature.\n\n- As far as I know, the ideas are novel.\n\n- The authors make a strong empirical case for their algorithm.\n\n- I'm a bit unsure about the significance of the algorithm, beyond the empirical results shown in the paper. I'm not sure whether the paper is sufficiently ground-breaking to have a significant impact on the broader reinforcement learning literature.", "weaknesses": "- I think the authors are a bit loose with their arguments about human cognition. It is hotly debate to what extent cognition depends on language in a strong way. It also important to note that one can endorse a \"language of thought\" hypothesis about high-level cognition without endorsing the hypothesis that this corresponds to natural language. In any case, I appreciate that these points have little bearing on the substance of this paper.\n\n- Eq. 1 could benefit from more explanation.\n\n- Please state what error bars show in figures.\n\nUPDATE: the authors have addressed my comments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and valuable feedback. We aim to address the concerns in the following:\n> I think the authors are a bit loose with their arguments about human cognition. \n\nWe thank the reviewer for bringing this up and agree with the fact that it is not clear how cognition depends on language. As mentioned by the reviewer, we have just mentioned them as part of conceptual motivation and focused on the problem of designing novel methods for efficient exploration. \n> Eq. 1 could benefit from more explanation.\n\nWe thank the reviewer for pointing this out. To clarify this, we have adjusted the writing between lines 83-89 to:\\\nFor a trajectory $\\tau=(s_1,a_1,...,a_{h-1},s_h)$ of length $h$, we want to compute the state visitation distribution to estimate the entropy. Each state within the trajectory can be formally expressed as a vector by first encoding the state $s_t$ as a one-hot bit vector $e_{s_t}$. The h-step state visitation distribution for $\\tau_h$ can be computed by marginalizing across the time steps:   \n$$\\xi_{\\gamma,\\tau} = \\sum_{t=1}^h \\gamma(t) e_{s_t},(Eq. 1)$$\nwhere $\\gamma: \\mathbb{N} \\to [0, 1]$ is the *discount function*  (we denote the set of positive integers with $\\mathbb{N}$), such that $\\sum_{t=1}^h \\gamma(t)=1$. Using the normalization in the discount function is necessary as it ensures that $\\xi_{\\gamma,\\tau}$ is a probability vector. We note that this use of a discount function is distinct from using a discount factor in common RL algorithms such as Q-learning but using a discount function is necessary as we will elaborate in the following section. The expected state visitation distribution for a policy $\\pi$ can be obtained by generating multiple trajectories using $\\pi$ and computing the average across them to get the expected state visitation distribution, denoted by $E_{\\tau} [\\xi_{\\gamma,\\tau}]$. \n\n> Please state what error bars show in the figures.\n\nWe mentioned in line 237 in the paper that the error bars denote the 95% confidence interval. However, we agree with the reviewer and have added this detail in the caption of the figures for more clarity.\n\n> I think the general usefulness of this approach will depend on how it can be applied beyond the maximum entropy exploration setting.\n\nWe agree with the reviewer that the proposed method will have more impact when applied to broader scenarios. Prior methods on maximum state entropy exploration were optimized to have optimal entropy across multiple trajectories of long length. However, to extend such methods to general tasks there is a need for more efficient policies that can explore the state space with minimal interactions. We believe $\\eta\\psi$-Learning by learning to explore efficiently within a single episode of limited length is a step towards using such policies for standard RL tasks. In the paper, we demonstrate the comparison of $\\eta\\psi$-Learning with Meta-RL methods where exploration is required at the beginning to find rewarding states efficiently during evaluation (Figure 4(c)). \n\nWe also added an additional experiment on a sparse MountainCar environment where the agent is rewarded only after reaching the goal state. Such tasks demand exploration at the start to gather rewarding transitions to improve sample efficiency. We compare with the following baselines: random agent,  TD3 [1], TD3 combined with count-based bonus as an intrinsic reward (TD3-Count), and TD3 combined with first occupancy bonus [2] as an intrinsic reward (TD3-First). We also propose a variant of our method combined with TD3 and call it TD3-$\\eta\\psi-Learning$, which learns 2 critics- one to estimate the SR as mentioned in Algorithm 2 ($Q_{expl}$), and the other to estimate the Q-function conditioned on the current state as done in TD3 ($Q_{ext}$). Analogous to TD3, the latter critic is learned using extrinsic rewards. Lastly, to update the actor, the agent optimizes for the overall Q-function which is defined as the linear sum of both Q-values based on extrinsic rewards and entropy-based term: $Q_{total} = Q_{ext} + \\beta Q_{expl}$. \n\nFigure 4 In the rebuttal pdf presents the results on Sparse MountainCar environment, where the proposed method outperforms the baselines. We have added this experiment with a pseudo-code for the TD3-$\\eta\\psi$-Learning and leave it for future work to leverage this approach for harder exploration tasks.\n\nWe hope we addressed most of the concerns and hope you would be willing to increase your score.\n\n#### References\n[1] Fujimoto et al., \"Addressing function approximation error in actor-critic methods.\" ICML’18.\\\n[2] Moskovitzet al., \"A First-Occupancy representation for reinforcement learning.\", ICLR’22\n"}, {"review_id": "UU4j1UpWOn", "reviewer": "Reviewer_RqRN", "summary": "This paper addresses the problem of maximum state entropy exploration in environments without rewards. Especially, it proposes a method to learn an history-based policy maximizing the entropy over the states sampled in a single trajectory. The method, called $\\eta\\psi$-Learning, combines predecessor representations, to keep memory of the previously visited states, and successor representations, to predict the states that will be visited in expectation under the current policy. The introduced algorithm is tested against MaxEnt in a set of toy domains and some continuous control tasks, it is also briefly tested against VariBAD in gridwolrd domain.\n", "questions": "This is an overall interesting paper, tackling a relevant problem raised by (Mutti et al., 2022a) on how to learn non-Markovian policies for maximum state entropy exploration efficiently. Especially, the authors propose to circumvent the inherent computational intractability of the problem with a well-motivated function approximation approach, in which the current decision is conditioned on a compact representation of the history and a forecast of the future state visitations under the policy.\nAlthough the paper does not introduce particularly novel or surprising ideas, it presents the method with clarity and showcases a brilliant performance for $\\eta\\psi$-Learning, at least in comparison with MaxEnt. While those might be sufficient reasons for acceptance, I believe that including a discussion on how this procedure can be scaled up to more challenging domains, such as image-based tasks, would make for a significant leap in the value of the paper.\n\n*(Major. How to scale up the approach?)*\nThe experiments show a remarkable improvement over MaxEnt, but previous works (e.g., Mutti et al., 2021) have demonstrated how Markovian policies maximizing the state entropy can be learned in challenging domains. Instead, it is unclear how the predecessor and successor representations of $\\eta\\psi$-Learning can be scaled to truly high-dimensional settings. While the method may be trivially adapted to continuous settings via discretization, it is unclear whether it can match the performance of previous works based on $k$-NN entropy estimators. Can the authors discuss avenues to scale their approach to high-dimensional domains? Estimating $\\psi_\\theta$ in practice would be significantly easier than state density estimation?\n\n*(Estimating the state visitations instead of the entropy)*\nIn $\\eta\\psi$-Learning, the quality of an action is evaluated in terms of the future visitations it will induce under the policy, from which the entropy of the trajectory can be then computed. However, the task of estimating the future state visitations seems strictly harder w.r.t. what is really needed to make an optimal decision, i.e., an estimate of the entropy that future visitations will induce. I am wondering whether there is a way to directly target entropy estimation instead of future state visitations in $\\eta\\psi$-Learning.\n\n*(Experiments. MaxEnt performance)*\nThe learning curve of MaxEnt is quite underwhelming: While the inferior performance of Markovian policies against $\\eta\\psi$-Learning is reasonable, I would have expected to see some learning progress for MaxEnt as well, especially in domains in which the random policy is far from the optimal strategy, such as in ChainMDP and RiverSwim. Can the authors clarify what is happening with the learning curve of MaxEnt?\n\n*(How the approach relates to Forward-Backward representations?)*\nA previous paper (Touati and Ollivier, Learning one representation to optimize all rewards, 2021) also addressed unsupervised reinforcement learning through representations of the past and future visitations, which they call forward-backward representations, bearing some similarity with the predecessor and successor representations of $\\eta\\psi$-Learning. Differently from this paper, they make learning these representations the actual unsupervised objective, and they advocate for directly employing forward-backward representations for zero-shot adaptation to the supervised task, instead of running state entropy maximizing policies first. Can the author compare $\\eta\\psi$-Learning with this previous approach, and explain whether the successor representation might be directly exploited in a supervised adaptation phase?", "limitations": "The paper does not include an explicit assessment of the limitations of the presented approach, which would add significant value to the paper in my opinion.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The paper proposes a simple yet effective method to learn non-Markovian policies that maximize the state entropy induced by a single trajectory;\n- The introduced method remarkably improves the performance of MaxEnt, here taken as a representative algorithm for maximum state entropy exploration with Markovian policies;\n- The ideas are presented with clarity and with some nice visualizations (e.g., Fig. 1 and 3) to support the intuition.\n", "weaknesses": "- It is unclear how the procedure can be scaled up to more challenging domains, e.g., image-based inputs;\n- The method is only tested against MaxEnt, which is not the state-of-the-art method for state entropy maximization, especially in continuous control tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and valuable feedback. We aim to address the concerns in the following:\n> MEPOL as baseline\n\nWe thank the reviewer for pointing this out and have added MEPOL[1] as baseline (Figure 1 of rebuttal PDF) and observe that $\\eta\\psi$-Learning outperforms MEPOL on continuous control tasks of Reacher and Pusher when compared over a single trajectory of finite length. \n> Major. How to scale up the approach?\n\nLearning to explore more complex tasks with high-dimensional input spaces would require using a better representation learning method and a mechanism to estimate successor and predecessor representations. For representation learning, existing methods that use auxiliary losses, inverse/forward dynamics, or random network-based features can be used. The more challenging task is learning the SR and future works can explore using Successor Measures[2] and ProtoValueNetworks[3]. \n\n> Estimating the state visitations instead of the entropy\n\nThank you for raising this point. While predicting future state visitations may seem harder than needed for entropy prediction, it is important to note that optimal decision depends on which states are visited multiple time steps into the future. It is possible that there exist more efficient algorithms for predicting this entropy, but to our knowledge such algorithms do not appear in the published literature and $\\eta\\psi$-Learning is the first of this kind. Another challenge with estimating entropy is that the estimator needs to adapt to the changing policy during training. In the proposed algorithm, this is mitigated as both the entropy and policy directly depend on the estimated SR vector requiring no additional updates to estimate entropy given the policy. In the revised version, we have highlighted this aspect and state that future work would involve discovering other more efficient methods for estimating the entropy induced by future state visitations.\n\n> Experiments. MaxEnt performance\n\nIn the MaxEnt paper, the evaluation was done by computing the state visitation distribution across multiple trajectories. However, in this work, we focused on learning policies that can optimize the entropy and attain optimal coverage within a single trajectory. In Appendix H.2, we evaluated MaxEnt across multiple trajectories and showed that the performance of MaxEnt improves with the number of trajectories. However, on Reacher is a harder task to solve as the state space and action space are complex compared to the grid-based environment, we see that the performance of MaxEnt improves during training (Figure 4(a) in the main paper). Furthermore, a random policy was found to have small coverage of the state space even across multiple trajectories as the agent starts at one of the corners in the state space and needs to be efficient to cover the state space.\n\n> How the approach relates to Forward-Backward representations?\n\nThank you for pointing out this connection. Intuitively, the Forward-Backward representations capture similar state visitation statistics as the predecessor and successor representation used by $\\eta\\psi$-Learning. Mathematically, the forward-backward (FB) representation factorizes the Q-function in an RL setting in a very different way than the $\\eta\\psi$-Learning algorithm. The FB method also focuses on a reward-maximization setting instead of exploration and are only conditioned on states whereas the $\\eta\\psi$-Learning algorithm conditions these representations on trajectories. During training, the focus of FB learning is on representation learning using an offline dataset where it is assumed that the agent does not have to explore the environment. The learned FB representations are then used to solve multiple different tasks using the same representations, assuming that reward parameterization is known. However, the $\\eta\\psi$-Learning algorithm learns exploratory policies that could be used to initially explore an unknown task to determine this reward parameterization. As suggested by the comment, the $\\eta\\psi$-Learning algorithm complements the FB method. We believe that integrating the two systems into a cohesive RL agent is an interesting avenue for future research and have added this discussion to the paper.\n\n> The paper does not include an explicit assessment of the limitations\n\nWe have added a section titled limitations in the paper. We mention the points below in brief and have expanded on them in the paper. \n1. *Scaling to high-dimensional inputs:* We used the same points from the discussion above on scaling the method.\n2. *Environments with changing dynamics:* Currently, the method is limited to exploring within the same environment where transition dynamics do not change, and extending to procedural environments is hard as it requires SR vectors that can adapt to the changes in the environment and we leave it for future research.\n3. *Architectural priors for estimating SR:* The successor representations use a GRU to encode prior states and future research can explore having better architectures like Transformers or S4 that have better long-term memory.\n4. *Estimating predecessor representation:* Future research can also explore learning predecessor representation vectors as done in [4] to improve sample efficiency. \n\nIn addition to the limitations, we have added the points on state visitation instead of entropy and connection with FB representations in the discussions. We hope we addressed the concerns and would be happy to take more questions. We hope the reviewer will consider increasing the score. \n\n#### References \n[1] Mutti et al., \"Task-agnostic exploration via policy gradient of a non-parametric state entropy estimate.\" AAAI’21.\\\n[2] Touati et al., \"Learning one representation to optimize all rewards.\" NeurIPS’21.\\\n[3] Farebrother et al., \"Proto-value networks: Scaling representation learning with auxiliary tasks.\" ICLR’23.\\\n[4] van Hasselt et al., \"Expected eligibility traces.\" AAAI’21."}]

Author rebuttal:
Firstly, we thank the reviewers for their time and constructive feedback. We hope to address the concerns during the rebuttal and would be happy to answer more questions. 

In this work, we developed an algorithm to learn exploratory policies at convergence that can explore the state space efficiently within a finite-length trajectory. Such policies can benefit generalization in different applications like Meta-RL and episodic exploration. Maximum state entropy exploration is a potential direction for learning such policies. However, prior works are not very efficient as they either learn a Markovian policy, optimize for the state coverage over multiple long trajectories, or learn a mixture of stochastic policies. Due to these shortcomings, they are not widely used for solving tasks in RL. To address these concerns, we introduce $\eta\psi$-Learning and demonstrate that the proposed algorithm can learn to efficiently explore the state space within a finite length trajectory. $\eta\psi$-Learning achieves this by combining predecessor and successor representation to estimate the state-visitation distribution and utilizing this to optimize the entropy-based objective. Mutti et al.’22 [1] theoretically showed that learning such policies that achieve zero-regret is NP-Hard and we develop a practical algorithm to solve such tasks. We hope that the proposed method bridges the gap of leveraging policies learned using maximum state entropy exploration for more complex tasks in RL. 

In Figure 4(c), we show that when compared with VariBAD, $\eta\psi$-Learning is more efficient at finding the reward function. We are adding a few more experiments to demonstrate the broader applicability of $\eta\psi$-Learning (discussed below):
1. To compare with other exploration algorithms in standard RL tasks, we performed additional experiments on the Sparse MountainCar environment. The agent receives a positive reward after reaching the goal position after which the episode terminates and no reward in other states. We chose this environment because the reward is sparse, and it is hard for the agent to discover the reward function as the agent needs to plan to explore the top of the hill. For the baselines, we compare with a random agent,  TD3 [2], TD3 combined with count-based bonus as an intrinsic reward (TD3-Count), and TD3 combined with first occupancy bonus [5] as an intrinsic reward (TD3-First).\
We also propose a variant of our method combined with TD3 and call it TD3-$\eta\psi$-Learning. For this, we propose to learn 2 critics- one to estimate the SR as mentioned in Algorithm 2 ($Q_{expl}$), and the other to estimate the sum of extrinsic rewards conditioned on the current state similar to TD3 ($Q_{ext}$). Lastly, to update the actor, the gradients are obtained using the overall Q-function which is defined as the linear sum of both Q-values based on extrinsic rewards and entropy-based term: $Q_{total} = Q_{ext} + \beta Q_{expl}$. We have added a pseudo-code of this algorithm in the Appendix of the paper.\
Figure 4 in the rebuttal pdf presents the results on the Sparse MountainCar environment. We compare two metrics- Return and Average Steps taken to reach the goal state across 5 seeds. The Average Steps metric highlights if the agent learns to solve the task with minimal interactions. We plot the mean and 95% confidence interval in shading. Through our experiment on Sparse MountainCar, we demonstrate that the proposed method can improve efficiency in standard RL tasks, especially in sparse reward environments. Future works can leverage the proposed extension in POMDP setting with high-dimensional inputs like images.
2. In this experiment, we wanted to show that $\eta\psi$-Learning can be scaled to high-dimensional space and conduct an experiment on the HalfCheetah environment. We propose to learn successor representations for larger state spaces by using ideas similar to ProtoValueNetworks [3]. To learn SR and predecessor representation, we discretize each dimension of the state space into K bins. Thus, a continuous state can be converted to |S| one-hot vectors where each vector is of K dimensions. The overall entropy and coverage are calculated by averaging the entropy and coverage over each dimension of the state space. We have used MEPOL [4] as the baseline and used the author’s implementation for our experiments.  We observed $\eta\psi$-Learning outperforms MEPOL on entropy and coverage metrics when evaluated over a single trajectory of 1000 steps~(Figure 2 of rebuttal pdf). Through this experiment, we wanted to show that the proposed method can be scaled to larger state spaces and believe future work can explore scaling them to more complex environments.

In the above experiments, we show that the method can be applied to tasks with rewards and can be scaled to environments with high-dimensional state spaces and leave it for future work to scale to more complex environments. 

We hope we addressed most of the concerns during the rebuttal and would be happy to answer further questions. 

#### References
[1] Mutti et al., "The importance of non-markovianity in maximum state entropy exploration." ICML’22.\
[2] Fujimoto et al., "Addressing function approximation error in actor-critic methods." ICML’18.\
[3] Farebrother et al., "Proto-value networks: Scaling representation learning with auxiliary tasks." ICLR’23\
[4] Mutti et al., "Task-agnostic exploration via policy gradient of a non-parametric state entropy estimate." AAAI’21.\
[5] Moskovitz et al., "A First-Occupancy representation for reinforcement learning." ICLR’22.

Meta-review: This paper proposes an maximum state entropy exploration method, called $\eta \psi$-learning. The idea is to maximize the state entropy of finite length trajectories and to combine predecessor and successor representations.

Reviewers appreciate the novelty and clear presentation of the idea, as well as the good empirical performance on toy domains and some continuous control tasks comparing with MaxEnt. Concerns regarding more exploration methods should be taken as baselines were answered by authors providing additional experiments on Sparse MountainCar environment. Concerns of how the proposed method could be scaled and perform in higher dimensional settings were partially addressed by additional results on HalfCheetah.

While reviewers agreed that the paper makes a good contribution to exploration methods, we recommend the authors to include also the discussions and clarifications about the importance of predecessor, limitations, as well as how to scale up the methods to more complex scenarios into next versions.
Decision: Accept (poster)