Discrete State-Action Abstraction via the Successor Representation
Authors: Amnon Attali
Pedro Cisneros-Velarde
Marco Morales
Nancy Amato
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
abstraction
successor representation
options
discrete
sparse reward
representation learning
intrinsic motivation

Abstract: While the difficulty of reinforcement learning problems is typically related to the complexity of their state spaces, Abstraction proposes that solutions often lie in simpler underlying latent spaces. Prior works have focused on learning either a continuous or dense abstraction, or require a human to provide one. Information-dense representations capture features irrelevant for solving tasks, and continuous spaces can struggle to represent discrete objects. In this work we automatically learn a sparse discrete abstraction of the underlying environment. We do so using a simple end-to-end trainable model based on the successor representation and max-entropy regularization. We describe an algorithm to apply our model, named Discrete State-Action Abstraction (DSAA), which computes an action abstraction in the form of temporally extended actions, i.e., Options, to transition between discrete abstract states. Empirically, we demonstrate the effects of different exploration schemes on our resulting abstraction, and show that it is efficient for solving downstream tasks.

Under review as a conference paper at ICLR 2023
DISCRETE STATE-ACTION ABSTRACTION VIA THE SUCCESSOR REPRESENTATION
Anonymous authors Paper under double-blind review
ABSTRACT
While the difficulty of reinforcement learning problems is typically related to the complexity of their state spaces, Abstraction proposes that solutions often lie in simpler underlying latent spaces. Prior works have focused on learning either a continuous or dense abstraction, or require a human to provide one. Information- dense representations capture features irrelevant for solving tasks, and continuous spaces can struggle to represent discrete objects. In this work we automatically learn a sparse discrete abstraction of the underlying environment. We do using a simple end-to-end trainable model based on the successor representation and max- eax-ontropy regularization. We describe an algorithm apply model, named Discrete State-Action Action Abstraction (DSAA), which computes an action abstraction in the form of temporally extended actions, i.e., Options, transition between discrete abstract states. Empirically, we demonstrate the effects of different ex- ploration schemes on our resulting abstraction, and show that it is efficient for solving downstream tasks.
INTRODUCTION
Reinforcement learning (RL) provides a general framework for solving search problems through the formalism of a Markov Decision Process (MDP); yet with that generality, it sacrifices some basic properties one might expect of search algorithm. In particular, one should not explore state multiple times, which is why basic search, such as Dijkstra's is algorithm, keeps track of the explored frontier. Basic search methods perform well when state and action spaces are small and discrete, but don't necessarily translate to more complex environments, such as large or continuous ones.
Humans have several intuitive ways to efficiently explore in complex scenarios. One is by abstract- ing states, thereby exploring a simpler, more structured model of the environment. For example, consider searching for an exit in large room using only touch: we would never blindly roam the center, but rather follow the walls. By abstracting states based on the property "can contain exit", we greatly reduce the set of states we have to explore in the first place. Another closely related way explore efficiently is by abstracting actions. Ingrained skills, or temporally extended actions, im- pose a prior the types of action sequences that help solve problems. For example, when exploring we don't move forward and then immediately backwards Randomly choosing the next direction to move rarely a good idea, and skills ensure that we explore new environments efficiently. In this work we are concerned with incorporating the intuitive concepts of state abstraction and action abstraction into reinforcement learning.
Our method for state abstraction is based on the Successor Representation, which intuitively charac- terizes states based on "what happens after visiting this state". By learning a discrete state abstrac- tion, we take advantage of a simple and natural definition for action abstraction: abstract actions are policies which help the agent navigate between pairs of abstract states (Abel al. 2020). We motivate our interest in discrete abstractions in two ways. Firstly, many of the decisions an agent must make the world are discrete and depend on discrete objects or properties. For example, the length of the optimal path out of room does not change continuously as a function of the number of doors. While we can still model such decision problems using continuous representations, is known that discrete metrics cannot be perfectly embedded in continuous spaces (Bourgain) 1985), and it has been shown empirically that policies trained in such continuous spaces struggle precisely points of discontinuity (Tang & Hauser 2019).

---

Under review as a conference paper at ICLR 2023
The second motivation is that classical algorithms for planning in discrete spaces are better under- stood and provide stronger guarantees; in fact, we often deal with continuous spaces by discretizing them with the help of local planners (Kavraki et al., 1996). Our action abstraction is like local planner, except learned rather than specified ahead of time. Moreover, our discrete abstraction rep- resents an explicit reduction in the size of the state space, in which both the depth and branching factor of future search can be easily controlled. Thus, it is simpler and more efficient to reuse it to navigate the environment.
1.1 CONTRIBUTIONS
Our main contribution is a novel method learn a discrete abstraction by partitioning an arbitrary state space from dataset of transitions which explore that same space. In particular, we cluster states with a similar Successor Representation (SR) as being part the same abstract state. In- tuitively, if the dataset of transitions visits similar states are in turn marked as similar. Unlike prior works on the SR (e.g.. [Machado] et al. (2018b); |aaeehh al. (2019)), our approach is end-to-end trainable and uses comparatively weaker max-entropy regularization. Our neural network model resembles a discrete variational au- toencoder, in which an encoder computes the abstraction and decoder computes the SR.
generated by some policy, states from which that policy
To demonstrate the effectiveness of our method, we propose an algorithm, Discrete State-Action Ab- straction (DSAA), which creates discrete state-action abstraction pair, using options for modeling the action abstraction. Since the SR depends on the policy used to generate data, we report the effect of changing the exploration method on the resulting abstraction, in contrast to prior work which has focused on uniform random exploration. We additionally compare DSAA to related works on both discrete and continuous tasks, demonstrating the value of learning a simple reusable representation.
2
BACKGROUND
2.1 REINFORCEMENT LEARNING
We consider the model-free reinforcement learning (RL) problem with an underlying infinite- horizon Markov Decision Process (MDP): M (X, 7, 20). with state space X, action space A, unknown environment dynamics p(a' x,a) giving the probability of transitioning to state x' having taken action at state x, reward function r X' x A + [0, 1], discount factor 0 < < 1, and initial state Zo. Let 2t E X, a E AA be the agent's 's state and action respec- tively at time t, and (a; xx) be the agent's policy, determining the probability distribution of agent actions at state Zt. Given a policy æ, the expected return (i.e., discounted sum of rewards) the agent would obtain action a is taken initial state æ, is described by the Q-value function:
(²( Ep.
E ((r(z1, ag 20
where a, x-112) and Te+1 p(-|21, at).
The agent's goal is to compute a policy क which maximizes the expected return from the starting state zo, i.c., arg max; [=>= (x0,, a)).
Since the environment dynamics p is unknown, a common approach in RL is to iteratively improve an estimate of the Q-value function, while simultaneously exploring the environment using the in- duced policy. However, we highlight that when the reward function is sparse, such methods suffer from long and uninformed (unrewarding) random exploration phase.
2.2 OPTIONS FRAMEWORK
Sutton et al. 1999) presented the options framework to extend the classic formalism of an MDP to a semi-MDP, in which
replace primitive single-step actions with temporally extended policies in the form of options. An option an MDP is 3-tuple o = (Io, To. To), where I,, To S X are the initiation and termination sets respectively, and n. is policy that initiates in some state To Io and terminates in any state in the set To-
Intuitively, an option describes local subproblem of navigating funneling the agent between regions of the state space. A common approach is to create options so that the termination set of one lies in the initiation set of another, thus allowing for option chaining (Bagaria & Konidaris 2019). In
2

---

Under review as a conference paper at ICLR 2023
Figure I: We provide intuition regarding the successor representation in two room environment with black walls where each room has 8 x 8 cells and single open cell connecting them. We compute the euclidean distance [|v(() (b)3) between the SR of every cell and the SR of fixed reference state & shown in blue. The top row shows distances computed for a uniform random policy, and the bottom row for uniform random policy augmented with wall-hugging option. This option initiates next to any wall, and follows counterclockwise until there are no walls adjacent. We observe that the SR partitions the environment based on agent dynamies, and options have large effect on the SR: relative distances are significantly smaller when using the wall-hugging option.
general, the quality of the options depends on the partition of the state space, such that each option takes the agent to useful sub-goal. Our work can be viewed as a method for designing such partition based on the successor representation.
2.3 SUCCESSOR REPRESENTATION
The successor representation (SR) of state, also known the discounted state occupancy, models the visitation density of given policy æ starting from each state. In a finite discrete state space S we can simply keep count of these visitation frequencies in a matrix v E IR S|X [S] whose (u, v)-th entry is
Eppor
Σ
T
1
50
The SR state u is the u-th row of the matrix a. denoted (u)...
Much like the Q-value function of MDP, the SR satisfies Bellman-like equation which relates the SR of a state to its neighbors by
T - (u, v) Lu=v + BBappp w.r(w)) (s, v).
When the environment dynamics are unknown and we instead have dataset D of transitions col- lected using a policy æ, this equation can be used to learn an estimate the SR, eb + Ri which minimizes the so-called temporal difference (TD) eиrоr Es,''> [v(s) (1(s) + vv)(s)) where (ss) is one-hot encoding of the discrete state s (the s-th standard unit vector).
We highlight that the SR depends heavily on the given policy used to explore the environment. Past work has focused the setting where
uniform random policy (i.e., random walk), and so the properties and/or usefulness of the SR with more general policies remains an open problem. We provide some intuition regarding the effects of changing the underlying policy on the SR in Figure We experimentally explore these effects on our abstraction in Section 6.1
Prior works have focused on the eigenvectors of the SR, primarily taking advantage of its relation to the graph Laplacian (e.g., Machado et al. (2018b) and to the decomposition of the MDP value function in terms the SR (Hansen et al. 2019 Blier al. 2021). In this work we focus on the SR itself rather than its eigenvectors. Figure demonstrates that the SR acts state embedding where distance between states corresponds to similarity between their successors. Moreover, options have predictable effects the SR; states in an option's 's initiation set have states outside it. The above observations motivate our method: cluster using the SR as a similarity metric, and then train options whose initiation sets correspond each cluster.
similar SR relative to
3

---

Under review as a conference paper at ICLR 2023
3 RELATED WORK
3.1 REPRESENTATION LEARNING
One of the primary motivations for abstraction is that complex real world MDPs have simpler latent structure, and exploring this latent space is sufficient for solving environment tasks (Jiang et al. 2017). For example, two different images may be equivalent with respect to maximizing reward (e.g., the color of an object might be irrelevant for planning). As such, it is desirable to first compute latent space that preserves underlying structure, and only then solve tasks in that latent space (Lee et al. 2020). One type of abstraction is Bisimulation, in which the aim is to preserve properties of the original MDP, namely the value function or optimal policy (Biza et al. 2020 Zhang al. 2021).
We emphasize that our approach is from the unsupervised learning perspective, in which the aim to learn a representation without reward, and then transfer this representation arbitrary reward functions on the same MDP. Many unsupervised representation learning methods attempt to capture MDP dynamics via contrastive losses which bring states separated by short time differences closer together (Stooke et 2021 Erraqabi et al.] (021). These methods are said to capture features which the environment, thereby yielding efficient exploration
change slowly as the agent transitions (Li et al., 2021). Jonschkowski & Brock (2015) impose additional structure the latent space, motivated by real world priors such as Netwon's Laws..
As observed in section 2.3 the SR is another method for capturing long term environment dynamics with respect to an exploration policy. Like us, Ramesh et al. (2019) cluster states based on the SR, yet their method is restricted to discrete inputs, whereas ours learns from arbitrary input spaces in fully differentiable manner. Also like us. Giannakopoulos et al. 2021) learn a discrete abstraction, but they follow the common paradigm of using observation reconstruction inform the latent space, which acts as a powerful regularizer encoding information irrelevant to planning.
3.2 INTRINSIC MOTIVATION
Abstraction falls under the broader category of Intrinsic Motivation (IM) methods. IM methods provide an intrinsic reward to the agent to guide and structure the exploration process, which makes exploration more efficient in the absence of environment rewards (i.e., when rewards are sparse). Oudeyer & Kaplan (009) describe three types of IM: knowledge, competence, and abstraction.
Knowledge-based IM methods reward the agent for improving its knowledge of the environment. Strehl & Littman (2008) and [Bellemare et al. (2016) reward the agent for visiting novel states. Cu- riosity (Sekar et a (2020) rewards the agent for visiting states in which a trained transition model has high uncertainty, thus encouraging the policy to sample in those regions and improve the model. Competence-
IM methods reward the agent for accomplishing sub-tasks in the environment. They often train Universal Value Function Approximation (Schaul et al. 2015) and employ strate- gies such as Hindsight Experience Replay (Andrychowicz et al. (017) to iteratively improve the agent's 'ss competence. These goal conditioned policies often (c.g.. Nasiriany et al. (2019) define goals in a latent space trained from a variational autoencoder (VAE).
Abstraction- based IM methods typically reward the agent for exploring latent space. For example, Feudal Networks (Vezhnevets et al., 2017) trains manager worker system, where the manager maps observations to latent space and produces direction in that space, then the worker is rewarded for achieving this desired direction. Eigenoption Discovery (Machado et al. 20188) 202T) computes a deep SR, then its eigenvectors individual reward functions for set of options. They train the SR offline, using uniform random exploration policy.
DISCRETE ABSTRACTION VIA END-TO-END SUCCESSOR LEARNING
In this section we describe our model Mo. for learning a discrete abstraction given dataset of environment transitions D. See Figure 2 for a visual representation, and Appendix A.3 A.3 for a more detailed derivation of our model loss.
4

---

Under review as a conference paper at ICLR 2023
Gumbel categorical
reparameterization
(x)
v(((x))
X
V
v(p(x)) SS ,x(((x'))
Max Entropy E,(Hss)
(x, x') D
Figure 2: Our model Mø.v resembles a discrete variational autoencoder in which we replace the observation reconstruction decoder with successor representation module. Red arrows indicate the flow of gradients back through the models. The encoder & maps observations, æ to discrete abstract states s, and & learns the SR based on next state samples x' and the TD-error.
4.1 ABSTRACTION 6
We implement our discrete abstraction as a feed-forward neural network encoder é X A(N) which maps observations E X' to points on the N-simplex (i.e., a distribution over N abstract states). Our model resembles the encoder of a Discrete Variational Autoencoder (D-VAF), where we employ the Gumbel-Softmax (Jang et al. 2017) to sample from the output distribution. Thus, we regularize the distribution, as D- VA, to similar to a uniform distribution prior ((N) over N discrete states, by minimizing the KL-Divergence over a dataset of collected samples D,
CH(0 D)
E [DK x)) U(N)) R~D
[- (6( [x)].
a>d
which is equivalent to maximizing the entropy over D; H (((z)) E, b(x); log(d(x)):.
Intuitively, we motivate the use of such regularization as follows: a uniform prior encourages a par- tition of the environment into similar sized parts. Segmenting the state space into abstract states turns our original large MDP into set of smaller sub-problems restricted to the pre-image of each abstract state. From divide and conquer perspective, imately the same size; otherwise, we may end up with very large abstract states, in which computing the seemingly local options between them is just as hard as solving the original task.
would prefer these problems to be approx-
To minimize Eq. | the Gumbel-Softmax allows us to sample from the distribution while still back- propagating through it. We qualitatively verify in Appendix A.4 that this is necessary, and that treating & as a classifier using simple softmax activation insufficient.
4.2 SUCCESSOR REPRESENTATION v/
The successor representation acts decoder the encoder We implement it as a feed-forward neural network v ((N) + R.N and train using the TD error over a dataset of transitions D:
Lsn( o. D) = E
[v(((())
(Φ(z) + (x(((2))))
(2)
where (-)- indicates fixed target, treated as a constant during back- mack-propagattons
Back-propagating through & into the many-to-one 6 ensures that when ø maps two input states to the same abstract state, they should have similar SR under the induced abstraction. This effectively clusters, much as was done by Ramesh et al. (209)), but does so in latent space. We note that zero is a fixed point Eq. 2] meaning o = and v O minimizes the loss. As a consequence, prior works tend to compute their abstraction in other ways, e.g., by not back-propagating through 1 (Machado et al. 2018b) or resorting to dense regularization such as observation reconstruction (Kulkarni et al. 2016 Our work shows that with discrete abstraction, and with Eq. T as regularization. we avoid this degenerate case. In Appendix A..4 we demonstrate that clustering in the latent space learned by D-VAE decoder yields abstractions not conducive solving tasks in the environment.
5

---

Under review as a conference paper at ICLR 2023
Explore the environment Generate transition dataset
Given transition dataset D Learn abstraction &
Given abstraction & Train option policies 7T
Figure 3: DSAA uses an exploration policy π (e.g., explore randomly with set of options) to generate a dataset of transitions in the environment. Then the successor learning module described in Section 4.1 computes a discrete abstraction of the environment according to Vh, the SR induced by и. Finally, These options can be used to solve downstream tasks the environment, or they can optionally be used by some other exploration scheme generate new data for new abstraction.
train
of o-relative options which navigate between pairs of abstract states.
Algorithm Discrete State-Action Abstraction (DSAA)
1: function DSAA N, transition dataset 'D {(x, a, x.) ) xx p(. xr a)})
2: Initialize models Φ, t)
b With size N latent space Train abstraction with loss as Eq, 1+ Eq.
3: Ca(Ø, vb; D) LH (o; D) LsR(v;; o, D)
4:
Update (Ø, vh) E arg min LA
D> e.g., with SGD over D Initialize directed abstract graph > Add an edge for each abstract transition in data Train option policy from Φ ( to
5: G (V [N] E
(})
6:
E [(o(x). 6(x (I,x") E D)}
7:
O' (ou, (u, E)
8:
return Φ, v O'
9:
end function Note we can train new abstraction by exploring with this new set of options
THE DSAA ALGORITHM
We provide pseudocode for our algorithm, Discrete State-Action Abstraction (DSAA), in Algo- rithm and a pictorial representation in Figure 3
DSAA takes input dataset of transitions in the environment, trains abstraction & as described in section 4.1 and then produces set of o-relative options O (Abel et al.) 20200), which navigate from primitive states in one abstract state to another. This induces an abstract graph G, in which nodes correspond to abstract states and edges to options between them.
More specifically, for fixed number of abstract states N and dataset our algorithm produces:
1. The abstraction ø X [N]. Let o -(s) = {x E X d(z) = s}.
2. The successor representation model t [N] + N
3. An abstract MDP represented by the abstract graph G = (V, E). Much like Roderick et al. (2018), for every abstract state transition that occurs in the dataset add edge to the graph: [N] and = ((((z), E [N] x [N] (z, x') D).
4. Option policies Oa.s' O, where Os.s' (s), Ta.s', X' o (s)) for each s') E E. Nz.s' initiates in the preimage abstract state s and terminates upon leaving it. Na, is rewarded for transitioning into s' follows: r (I, 1 -,(x)='' where x' p(-12, a).
We note that this slight departure from our previous discussion of options, since we only reward the policy for specific transitions into the terminating

---

Under review as a conference paper at ICLR 2023
(a) states, explore uni- formly at random
(b) 8 states, expert data bottom right
(c) 16 states, leave first
(d) 16 states, noisy input
room option
Figure 4: Ma.e FourRooms with different exploration datasets. Each color is abstract state.
5.1 USING AN ABSTRACTION TO SOLVE TASKS AND MAXIMIZE REWARDS
From some starting state zo E X. given a goal state Zg E N. we can compute an abstract path in G, P2o.22 [50. .I.........., So = 6(00), 9k o(s,)]. To reach Tg we can now exe- cute the corresponding sequence of options, {ou,,. Ji=0 and finally explore solely within 84- In other words, have reduced the original exploration problem from the full state space X' just o (ő(x)) S X. We highlight that baseline exploration algorithms specifically struggle with long trajectories through bottleneck states, and demonstrated intuitively in Figure [and experimen- tally in Section 6 our SR based abstraction partitions the environment along bottlenecks.
1k11
If instead of goal state in the environment we given a reward function maximize, we simply explore using the trained options. In other words, we perform a lazy random walk on G, in which every step we select a random neighboring edge and follow the corresponding option policy. The walk is lazy because we allow for self-loop edges, whose options randomly explore without leaving the abstract state. We observe that this approach introduces an apploration-explotattiin trade-off: at each step the agent either explores within its current abstract state, exploits trained option to reach a new abstract state. The agent is trained in the standard semi-MDP fashion, where we take sums of rewards over temporally extended actions (Sutton et al. 1999)).
EXPERIMENTS
6.1 EFFECT OF CHANGING THE DATASET
In these first experiments we explore the effects of changing the input dataset on our model Ma.v- We report results in Figure 4 the FourRooms environment (Sutton et al., 1999) using (a) uniform random exploration, (b) expert data that takes the agent to the bottom right corner, (c) random exploration with options which exit the first room, and (d) random exploration with noisy input, where each state has a randomly sampled noisy bit that changes each time the state is visited making different visits seem different. In each case we train with the same parameters (c.g.. model size or loss hyper-panne parameters) and only vary the number of abstract states N. Figure 4(a) demonstrates that our abstraction learns the intuitive partition under random exploration. Figures 4(b) and [(c) show how the initiation sets of options (including expert policies) get grouped together. Finally, Figure [dd] demonstrates our model's 's robustness irrelevant features, it successfully captures environment dynamics (e.g., state proximity) despite the existence of distracting features.
6.2 COMPARISON TO RELATED WORKS
In these experiments we compare to two related works, Contrastive (Erraqabi et al. 2021) and Eigenoption (Machado et al. 2018b). Contrastive is representative of a classic approach to rep- resentation learning in RL, namely use contrastive loss to encode environment dynamics in latent space, and then guide agent exploration using distance to the latent goal as an intrinsic reward. Figure 5(a) shows example of such leamed latent space. Eigenoption is representative of how state of the art approaches use the SR, namely by taking the spectral decomposition of the SR (i.c., its eigenvectors) as basis in which to represent arbitrary value functions. Specifically, Higenop-
7

---

Under review as a conference paper at ICLR 2023
14-
18
26-
(a) Contrastive encoding
(b) An eigenoption
(c) A DSAA option
Figure 5: On the left we visualize 2-dimensional latent space learned through contrastive encoding where each point corresponds to one state from FourRooms. In the center we show an example eigenoption, see Appendix [A.3] for more examples. Finally, on the right we visualize an example of a DSAA option. Notice our options are restricted to the preimage of single abstract state (this makes them easier to train than eigenoptions). Lighter color indicates states where the option policies achieve higher value.
tions each eigenvector of the SR as individual reward for option. See Figure 5(b) for example an eigenoption. Finally, Figure ((c) shows an example of an option output by DSAA.
We test the FourRooms environment, where for all three algorithms train using initial random exploration phase without environment provided reward, then transfer to new tasks in the same environment. We highlight that the sparse nature of reaching specific state in the environment and the existence of bottleneck states in FourRooms makes this is relatively difficult task for standard RL. Figure 6 shows the average return of the three methods and Table demonstrates that DSAA is faster and more consistent in reaching a randomly chosen state in the environment. Eigenoptions suffers by not having an abstract state representation drive exploration towards the goal. Contrastive is slowed down relative to DSAA because it trains an underlying policy over the entire state space, and its shaped reward sometimes leads the agent into dead ends.
1.0
0.8-
Method
Mcan
Std
Iverage Betur
Random
30.30
45.94
Eigenoptions
8.66
10.61
Contrastive
5.37
4.36
random contrestive
DSAA 1.48
0.77
doas eigenoptions
Number of Episodes 100
Table 1: We report the first time each method finds the goal (i.e., diffusion time (Machado et al. 20186)). This captures the minimum number of episodes before one consis- tently solve the task, thus evaluating explo- ration efficiency while controlling for the ef- fects of training the underlying agent.
Figure 6: We report the average return each method achieves across episodes in the Four- Rooms environment. Results are averaged over 30 randomly chosen starts and goals with episodes of length 200 steps each. The vertical line is the first time random exploration finds the goal.
6.3 ARM2D: MAXIMIZING REWARDS IN A CONTINUOUS SPACE
In these final set of experiments we show the capability of DSAA to maximize rewards online in continuous control enviromment. Arm2D is continuous control task for three joint manipulator (robot arm) on 2D-plane (see Figure ((a).. The arm must move an object (ball) down below certain height, despite the starting below the ball, at which point only it obtains non-zero
8

---

Under review as a conference paper at ICLR 2023
0
-10
-5
-20
-35
-30
-20
-10
20
20
30
(a) Arm2D environment
(b) Samples different abstract states
(c) state example abstract graph
10-
20
60
Auarage
0.4-
dssa, Jeasy
dsea hard
base, hard
0.0
600
800
1000
Number Fpikodes
(d) Abstract state visualization
(e) Online RL comparison results
Figure 7: Arm2D environment experiments. In (b) we visualize arm positions at boundaries between abstract states; and in (d) show 2D slice of the 5D state, colored by abstract visualize an example abstract graph for 8 abstract states. Finally in (e) we show return curves for DSAA and Soft Q-Learning baseline on both the "hard" and "easy" tasks shown (a), averaged over 10 random seeds. The standard deviations, which we only visualize for the "easy" task, demon- strate the consistency of our method.
In (c) we
reward: the lower the height the ball must reach, the more difficult the task, since the sparse reward is more distant. The state space is 5-dimensional, including the three joint angles and the 2D object position. For a more detailed description of the Arm2D environment, we refer to Appendix [A.6.]]
The results in Figure demonstrate that reward with few samples. Moreover, the iterative version of DSAA, which the output options are reused to train abstraction, makes exploration progress. In Appendix A.7 we show examples of abstractions for more complex versions of this environment.
simultancously learn abstraction and maximize
7 CONCLUSIONS AND FUTURE WORK
We presented method to perform discrete abstraction the state and action spaces of reinforcement learning problem using a dataset of transitions in the environment. Our model is based on the successor representation, grouping states together the agent's behavior after visiting those states is similar. We showed that despite past concerns that gradients from the successor representation would drive any abstraction towards a trivial fixed point, with simple max entropy regularization we can learn useful abstraction in the discrete setting, and do so in an end-to-end manner. Finally, we showed that DSAA agent equipped with our action abstraction can solve variety of downstream tasks.
limitation of our work is that while our method may help an agent explore the environment ficiently, that exploration is still heavily biased towards the region that has already been explored. Given this limitation, one direction for improvement to train a higher level policy to bias the walk over the abstract graph towards states which have been identified as the frontier (e.g., see Sekar et al. 2)220). Another interesting line of future work would provide theoretical guarantees on the conver- gence of clustering by successor representation, Finally, we recognize that despite their advantages, discrete representations can struggle to capture very large spaces, and combining discrete abstraction with continuous could be fruitful.
well other properties related to method.

---

Under review as a conference paper at ICLR 2023
8 REPRODUCIBILITY STATEMENT
All code for running our experiments will be made publicly available along with the final version of this manuscript. In particular, we will make available the reinforcement learning environments on which we test, the random seeds used for generating different experimental runs, and the implemen- tation code and configuration files for training our successor model and DSAA algorithm.
REFERENCES
David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. Value preserving state-action abstractions. In International Conference on Artificial Intelligence and Statistics, pp. 10.11634 1639-1650. PMLR, 2020.
Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abheel, and Wojeiech Zaremba. Hindsight experience re- play. Advances in Neural Information Processing Systems, 30, 2017.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In 7th Interna- tional Conference on Learning Representations, 2019.
Mare Bellemare, Stiram Srinivasan, Georg Ostrovski. Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances in Neural Information Pro- cessing Systems, 29, 2016.
Ondrej Biza, Robert Platt, Jan- Willem van de Meent, and Lawson LS Wong. Learning discrete state abstractions with deep variational inference. arXiv preprint arXiv:2003.04300. 2020.
Léonard Blier, Corentin Tallec, and Yann Ollivier. Learning successor states and goal-dependent values: A mathematical viewpoint. arXiv preprint arXiv:2101.07133 2021.
Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1):46-52, 1985.
Akram Erraqabi, Mingde Zhao, Marlos Machado, Yoshua Bengio, Sainbayar Sukhbaatar, Ludovic Denoyer, and Alessandro Lazaric. Exploration-driven representation learning in reinforcement learning. In ICML 202/ Workshop on Unsupervised Reinforcement Learning, 2021.
Petros Giannakopoulos, Aggelos Pikrakis, and Yannis Cotronis. Neural discrete abstraction of high- dimensional spaces: A case study in reinforcement learning. In 2020 28th European Signal Processing Conference (EUSIPCO), pp. 1517-1521. IEEE, 2021.
Steven Hansen, Will Dabney, Andre Barreto, Tom Van de Wiele, David Warde-Farley and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. arXiv preprint 1rXivv1906.05030 2019,
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizatioo with gumbel-softmax In 5th International Conference Learning Representations, 2017.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning. pp. 1704-1713. PMLR, 2017.
Rico Jonschkowski and Oliver Brock. Learning state representations with robotic priors. Au- tonomous Robots, 3903):407-422 2015.
Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4)5566-580 1996.
Tejas Kulkarni, Ardavan Sacedi, Simanta Gautam, and Samuel Gershman. Deep successor reinforcement learning. arXiv preprint arXiv:1606.1 003600236, 2016.
10

---

Under review as a conference paper at ICLR 2023
Alex X Lee, Anusha Nagabandi, Pieter Abbeel, and Sergey Levine. Stochastic latent actor-critic: Deep reinforcement learning with a latent variable model. Advances in Neural Information Pro- cessing Systems, 33:741-752, 2020. 2020.
Siyuan Li, Lulu Zheng, Jianhao Wang, and Chongjie Zhang. Learning subgoal representations with slow dynamics. In 9th International Conference on Learning Representations, 2021.
Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew J. Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-5622 2018a.
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Míao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In 6th International Conference on Learning Representations, 2018b.
Marlos C Machado, Andre Barreto, and Doina Precup. Temporal abstraction in reinforcement learn- ing with the successor representation. arXiv preprint (tf:::211000544440 2021.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal-conditioned
policies. Advances in Neural Information Processing Systems, 32, 2019.
Pierre-Yve Oudeyer and Frederic Kaplan. What is intrinsic motivation? a typology of computa- tional approaches. Frontiers in neurorobotics, 1:6, 2009.
Rahul Ramesh, Manan Tomar, and Balaraman Ravindran. Successor options: An option discovery framework for reinforcement learning. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19, pp. 3304-333333 3310, 2019.
Melrose Roderick, Christopher Grimm, and Stefanie Tellex. Deep abstract q-networks. In AAMAS '18: Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, pp. 131-138, 2018
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In International on Machine Learning, pp. 1312-1320. PMLR, 2015.
Ramanan Sekar. Olch Rybkin, Kostas Danillidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervised world models. In International Conference on Machine Learning, pp. 8583 8592. PMLR, 2020.
Adam Stooke, Kimin Lee, Pieter Abbeel, and Michael Laskin. Decoupling representation learning from reinforcement learning. In International Conference Machine Learning, pp. 9870-9879. PMLR, 2021.
Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309-133) 2008.
Richard Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
Gao Tang and Kris Hauser. Discontinuity-sensiivi optimal control learning by mixture of experts. In 2019 International Conference Roboties and Automation (ICRA), pp. 7892-7898. IEEE, 2019.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International on Machine Learning, pp. 3549, PMLR, 2017.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invari- ant representations for reinforcement learning without reconstruction. International Conference on Learning Representations, 2021.
11

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 REVISIONS COMPARING TO RAMESH ET AL. (2019)
We add comparison to SuccessorOptions (Ramesh al. 2019). Figure shows the updated comparison plot and table, Figure 9 shows a comparison of the state partitioning produced by Suc- cessorOptions, compared DSAA. Figure TO shows examples of the options learned by Succes- sorOptions when using four clusters in FourRooms.
We emphasize that SuccessorOptions implemented on the discrete MDP for which it computes discrete SR, whereas our method is only given transitions in the environment using the continuous (x.y) coordinate of the state. Thus we simultaneously learn the discrete abstraction and the corre- sponding SR. This means that while SuccessorOptions must separately cluster states after computing the SR, we the clustering end-to-end. Moreover, even though our state abstractions are com- parable, our action abstraction performs significantly better since, while they navigate individual primitive states in the environment, we train options that transition between regions of the space.
Method
Mean
Std
Average Reaum
Random
30.30
45.94
0.6
SuccessorOptions
16.30
24.37
Eigenoptions
8.66
10.61
0.4
random
contrastive
Contrastive
5.37
4.36
0.2
dsee
DSAA 1.48
0.77
eigenoptions
Successoroptions
0.0
Epicodes
Figure 8: This new returns chart will replace Fig- ure
Table 2:
This table will replace Table Once again we emphasize the consistency of our method in finding the sparse reward. This consistency comes from the combination of state and action abstraction.
As expected, Successor Options (Ramesh al. 2019 performs similarly to Figenoptions, namely because both learn options which navigate to specific primitive states.
A.2 REVISIONS LEARNING AN ABSTRACTION FOR MONTEZUMA'S REVENGE
We train an abstraction for Montezuma's 's Revenge, the notoriously hardest problem in the Atari suite (Arcade Learning Environment Machado et al. (2018))). We show results of training 16 state abstraction in Figure T2 based on random exploration data. Notice that our model Ma. is capable of learning an abstraction that captures intuitively relevant aspects of the problem, such as the existence of ladders to climb. Moreover notice that relative to the results seen in Figure 5 of Eigenoptions (Machado et al., 2018b), we can use small number of abstract states and still learn something useful, rather than learning hundreds of options which then would require significant pruning for real applications. While these results don't immediately show the usefulness our state and action abstraction in solving Montezuma's 's Revenge, they demonstrate that Ma.v generalizes to significantly more complicated domains. Solving the full problem would require coupling our approach with proper exploration method which would produce the necessary dataset for learning the abstraction; a subject of future work.
A.3 EXPLAINING MAX ENTROPY
We would like solve the following optimization problem: given state space X compute an abstraction function 6 6:2. X + [N], and function vh [M] + N., which minimizes the SR temporal difference enror (Eq. 2) subject to entropy constraint:
12

---

Under review as a conference paper at ICLR 2023
04
2.0
0.
75
7,5
7.
125
125
15.0
150
13.0
00
2.5
3.0
10.0
125
15.0
17.
25
5.0
15.0
125
15.0
17.5
5.0
25
5.0
10.0
12.5
15.0
(a) cluster SuccessorOptions
(b) 8 cluster SuccessorOptions
(c) 16 cluster SuccessorOptions
23
2.5
25-
T
30.0
15.0
10.0
15.
15.
175
17.5
175
2.5
10.0
125
15.0
175
5.0
12.0
125
15.0
17.5
50
100
12.
15.
175
(d) DSAA with states
(e) DSAA with states
(I) DSAA
states
Figure 9: As expected, DSAA and SuccessorOptions partition the state space similarly. Cluster ters for SuccessorOptions are highlighted in red (our approach does not explicitly define center).
Figure 10: SuccessorOptions in FourRooms with 4 clusters and the corresponding options
min Ex (1) (1((()))) (6(x) G.4
(+(((²)))
s.t. H(xx) > k
where p(. x)) = E.p(- xxa)) a) and ox is the random variable over [N]. which assigns probability Pox (i) E,, (1x()=)) based on the proportion of X' that gets mapped by ø.
We now use the method of Lagrange multipliers and optimize over batch with stochastic gradient descent to derive the loss LA in Algorithm [ Experimentally find the method is sensitive to batch size, if the batch size is too small we fail to properly capture the entropy constraint.
A.4 ADDITIONAL ABLATIONS FOR THE FOURROOMS ENVIRONMENT
In the set of ablations shown in Figure 13 categorical reparameterization via Gumbel-Softmax as opposed to straightforward classification via Softmax, applied to the output logits of the abstraction model Φ. We also explore the effects of
qualitatively demonstrate the importance of stochastic
13

---

Under review as a conference paper at ICLR 2023
12
Figure 11: We additionally train options to directly go to the cluster centers for each SuccessorOp- tion. In Ramesh (2019) this the option they motivate (in prose), though the reward they provide mathematically (shown in Figure [0) is an approximation of this goal. Surprisingly these "desired" options perform worse, and so we display them here merely for completeness.
adding a weight coefficient B to the entropy term in the abstraction update loss as LA CH + BCSR-
Figure [4 we show that swapping our decoder with a classic reconstruction module and then clustering does not yield good abstractions.
A.5 RELATED WORK IMPLEMENTATIONS
We implemented the comparison methods "generously": for Eigenoption used the analytical Successor Representation based on the graph Laplacian in the discrete FourRooms environment rather than an empirical deep SR. We then compute eigenoptions and their negatives shown in Fig- ure 15 For Contrastive we note that the original paper (Erraqabi et al., 2021) only reports "acyclic" environments, whereas FourRooms contains multiple distinct homotopy classes of trajectories. We find that the method is harder to tune in such environment, demonstrating the known result that discrete metrics (of which a simple example is cycle of nodes with edge length 1) cannot be per- fectly embedded in euclidean space (Bourgain 1985). Their method therefore struggles with certain tasks because the shaped reward (which acts as a heuristic to bias exploration) sometimes leads the agent into dead ends.
A.6 ARM2D ENVIRONMENT DETAILS
A.6.1 DESCRIPTION
The action space consists of 6 discrete actions: each one the 3 arm joints has two actions which increment decrement its angle by d degrees. For our specific simulations we set = 1 degree. Each joint is limited between -90 and 90 degrees. The state spaces consists of features: the joint angles and the (x.y) coordinate of the ball. While the joint angles are discretized (by 5), the ball location remains continuous. Each episode was limited to 5000 steps at which point we reset the environment by bringing the arm back to joint angles [0, 0, 0] (horizontal position of the arm), and the ball to (æ, 3) (13, 13). The fixed end of the robot arm is located at position (0, 0). The environment reward is a sparse 0 or 1, where 1 is only given to the agent if it moves the ball below the green line ("easy" task at height y 11) or red line ("hard" task at height = 9) shown in Figure 7(a)
We provide more detail about the Arm2D environment of Section 6.3
A.6.2 MODEL ARCHITECTURSS
Our algorithm trains three models: th, ,...' We structure all three as simple feed-forward neural networks. We report the specific values used for the experiments Section 6.3
0: X A(N) has two hidden layers with 128 and 256 neurons, and LeakyReLU acti- vation functions. The input is the 5 dimensional primitive state I, and the output has N neurons, one for each abstract state, which passed through a Gumbel-Softtax activation with temperature parameter For these experiments used N 8, 0.5.
14

---

Under review as a conference paper at ICLR 2023
A.A. AARA
Figure 12: For each of 16 abstract states visualize samples of of the character's 's location in the environment in red. The abstraction is trained after exploring the environment using uniform ran- dom actions for 200,000 steps. The encoder-decoder model architecture used is the same in other experiments reported in the paper, with similar hyper-parameter settings. This qualitative evaluation primarily demonstrates that despite the complexity of the environment our model (and correspond- ing loss) is capable of learning an interesting environment partition. In particular, even without reconstruction enrr regularization term our loss we not collapse the trivial abstraction.
15

---

Under review as a conference paper at ICLR 2023
(a) Softmax with /
(b) Softmax with 10
Softmax with 100
Figure 13: In these ablation experiments we train an abstraction with 4 abstract states and uniform random exploration. demonstrated Figure each abstract state should intuitively correspond to one of the rooms. Replacing Gumbel-Softmax with Softmax leads to poor abstractions: we ob- serve that abstract states occupy more than one room, including the bottleneck connections between rooms, even disjoint across two rooms (e.g., abstract state 0 in (b)), which did not occur with Gumbel-Son -Sffta- Moreover, we observe that the size of each abstract state remains unbalanced
with large weight coefficient 3 for the entropy term in the loss.
3.0
0.8
25
25-
5.0
75
22.5
225
-05
17.5
-10
0.0
255
5.0
7,5
10.0
12.5
15.0
17.5
(a) FourRooms, 4 abstract states
(b) FourRooms, 8 abstract states
Figure 14: Using a D-VAE (with a reconstruction loss instead of our SR error) generates ab- stractions that do not take into account agent dynamics and are therefore poor for planning.
v A(N) N has hidden layers with 64 and 128 neurons and LeakyReLU activa- tion functions. It takes as input the output from & and maps it to N neurons output.
Finally, we group our option policies as single model with shared parameters except for the final output layer. More precisely, we train neural network with four hidden layers of 64, 128, 256, 512 neurons and LeakyReLU activation. takes as input æ concatenated with Φ(x), which in our of N abstract states with state vector of dimension 5, results + 5 = 13 imput states. Then for each option T.,s' we have a single linear layer with no activation that maps from the 512 neuron embedding to the discrete actions of our agent, which in our case of N = 8 abstract states and [A| = 6 discrete actions, results in 8 48 outputs. We note there other ways example by not sharing parameters between each option policy.
model the option policies, for
A.6.3 PAPERRPARAMMTER DETAILS
We now describe the hyperparameter settings used in the experiments shown in Figure 7 We highlight that we did not conduct large scale parameter search for the optimal configuration of the hyperparameters. In this sense results demonstrate algorithm without excessive tuning.
16

---

Under review as a conference paper at ICLR 2023
(a) Option Cn
(b) Option en
(c) Option -6n-1
(d) Option Cn-1
(e) Option
Cn-
(l) Option Cn-2
(g) Option -
(h) Option en-3
The first four eigenoptions and their negatives. Terminal states are shown in black, and regions of higher value colored lighter (yellow opposed to green).
Figure 15:
We roll out each episode for 5000 steps and set the replay buffer size for the option policy to 100, 000 transitions (20 episodes). This is the same replay buffer which we use to train the abstraction, and consequently we set the number of exploration steps (E_iters in Algorithm T to 100, 000 well. We use Adam optimizer with learning rate 0.001 and batch size 512 for updating both T.,s' and o, el (which are updated in tandem and the successor representation have a discount factor 7, which we set to 0.95. use a target Q model for computing the temporal difference target, which updates with delay behind the online model of 20 iterations. We reward each option policy when transitions to the correct next abstract with 200 reward points this reward needs to be high enough to balance the entropy based reward the soft policy receives on each transition, but is otherwise arbitrary.
pair). Both the update equations for Q-learning
We implement models using Py PyToch, without any external learning libraries outside imple- mentations of Soft Q-learning. We run on CPU using an Intel(R) Core(TM) 19-10980XE CPU @ 3.00GHz. The code can be found as part of the Supplementary Material.
A.7 SCALABILITY OF M
As mentioned in the final sentence of Section 7 discretization is not always the best approach for particularly large spaces in which one may want to combine discrete and continuous representa- tions. Nevertheless, in this section demonstrate that method for abstraction scales to both image representations and high dimensional agents. Figure dedeonnsraass that when using a more complex input representation, such as image, model is still capable of learning a reasonable abstraction consistent with prior results. Figure 17 shows learned abstraction for a 10 joint robot arm in the plane, with one joint fixed at a point and all others allowed to vary between and m. Note that self collisions are not valid configurations.
17

---

Under review as a conference paper at ICLR 2023
29
123
125
125
120
150
16
183
179
7.9
10
25
10.0 12. 1..
(a) FourRooms, 4 abstract states
(b) FourRooms, abstract states
(c) Arm2D, 16 abstract states
Figure 16: Using the same environments reported in the main body of the paper, demonstrate that replacing the input representation with images still yields qualitatively reasonable (and similar to previous) discretizations of the space. In FourRooms the input is 19 x 19 361 pixels, with single pixel sparsely marking the agent location. In Arm2D the joint angles are replaced by 62 x 62 = 3844 pixels depicting the arm. Note in Arm2D the resulting discretization is much less smooth relative to Figure 7(d)
Samples of arm positions at each of 16 abstract states
0
4
12
1
13
2
6
10
14
3
11
15
For each abstract state we visualize samples of configurations of 10 joint arm. Notice that some states, such as and 4, have no arm configurations. One could increase the max entropy coefficient term to encourage the model to more evenly distribute the samples. There is no obvious intuitive partitioning of such a configuration space in the absence of narrow passages which would be formed by obstacles.
Figure 17:
18


Reviews:
[{"review_id": "tA0ETBzzHIa", "reviewer": "Reviewer_vZz4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to use a dataset of environment transitions to divide states into N discrete clusters. They propose a Discrete VAE architecture that encodes a state into one of N discrete states and then decodes it into its successor representation. The encoder is regularized by a uniform prior leading to similarly sized clusters of states and the decoder ensures states with similar Successor Representations have the same discrete cluster. Temporally abstracted actions (options) are trained to transition between the discovered state clusters. This procedure is shown to perform well in two simple environments: FourRooms (discrete) and Arm2D (continuous).", "summary_of_the_review": "The paper has original ideas and is written well. However, I am not yet convinced of the importance of the problem solved and method proposed, as it may be limited to toy tasks — both, in terms of the assumptions and the experiments. I would consider raising my score if these concerns could be addressed.", "strength_and_weaknesses": "## Strengths\n- The paper is clearly written, easy to follow, has a good structure and flow, and contains sufficient background to understand the method.\n- The idea of clustering states into a discrete set of clusters and using them for option learning is interesting and seems novel.\n- The method is simple, intuitive, and achieves the paper's desiderata of uniformly sized state clusters with similar Successor Representations.\n\n## Weaknesses\n- **Are the assumptions practical?**\n    + My main concern is that the assumptions required to make the method work do not seem to be practical and would not scale to complex tasks. For instance,\n        * The idea of defining state clusters only makes sense in small and closed environments. In unknown and complex environments, it is not even clear what the number of state clusters (and options) would be.\n        * The dataset of environment transitions should cover all the states in the environment, at least those that the downstream task would observe.\n        * In search-like tasks like mazes or Arm2D, the main challenge is reaching certain states using a reward. But this paper bypasses this problem of state exploration by assuming the dataset does most of the hard job. Therefore, it does not seem practical for most problems.\n        * Equally-sized state clusters: Depending on the task family, differently-sized clusters might make more sense, e.g., guided by reconstruction or environment reward or reachability of states or semantic properties (such as objects) of states.\n    + Are there realistic applications that would still fall under such assumptions and thus benefit from the proposed method?\n- **Experimental Evaluation**\n    + **Environments**\n        * While the proposed method can work in both discrete and continuous settings, I am concerned about the complexity of tasks it can scale to. The current environments are too simplistic and deterministic: even random exploration can find the goal in 30 episodes in the FourRooms environment. The prior work (Machado et al. 2018) also uses Successor Representations and shows results on the Atari domain. \n    + **Mismatch from claims**: While the paper claims (in the introduction) that discrete state abstraction is helpful to discover discrete objects or properties and for understandability, none of these benefits are exhibited in the experiments.\n    + **Baselines**: The use-case of the proposed method is in learning state abstraction and options unsupervisedly. However, several skill discovery methods, such as Pertsch et al. (2021), discover skills from unsupervised offline datasets and use them to accelerate downstream RL. Shouldn't such Hierarchical RL methods also be compared as baselines to demonstrate the importance of discrete state abstractions?\n\n[1] Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In 6th International Conference on Learning Representations, 2018.\n\n[2] Pertsch, Karl, Youngwoon Lee, and Joseph Lim. \"Accelerating reinforcement learning with learned skill priors.\" Conference on robot learning. PMLR, 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "biDgddonbQ", "reviewer": "Reviewer_icxB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose an approach to learn a discrete abstraction of an environment in reinforcement learning. The proposed approach creates abstract states using the successor representation (Dayan, 1993), reflecting the intuition that states should be grouped together based on \"what happens after visiting a state\", and creates abstract actions (options) that take the agent from one abstract state to neighbouring abstract states. The authors present an empirical analysis of the proposed approach in two domains: a gridworld with four rooms and a three-joint control task on a two-dimensional plane. \n", "summary_of_the_review": "The authors present a plausible approach to abstraction in reinforcement learning, building on several earlier ideas and methods. The main novelty in the paper is the specific way the successor representation is used in defining the abstract states. The approach could prove useful but the analysis in the current paper does not give the reader a good understanding of the behaviour of the approach and its strengths/weaknesses relative to existing methods.", "strength_and_weaknesses": "Strengths: \n\n-- The authors present a plausible approach to abstraction in reinforcement learning, building on several earlier ideas and methods. \n\nWeaknesses: \n\n-- The analysis and evaluation of the approach is quite limited. \n\nFirst, the authors explore the behavior of the proposed approach in a relatively narrow range of environments. The first domain is a small gridworld with four rooms. The authors state \"We highlight that the sparse nature of reaching a specific state in the environment and the existence of bottleneck states in FourRooms makes this is a relatively difficult task for standard RL.\" Not many people would agree with this statement. On the contrary, this is quite a simple task for reinforcement learning. This domain is not only easy but also has a very simple structure, and many alternative methods would identify very similar abstractions (e.g., those based on graph clustering). It is not a particularly informative environment. The second domain is more complex than the gridworld but still relatively simple. \n\nSecondly, the analysis in each domain is relatively limited and does not give the reader a good understanding of the behaviour of the proposed approach. For instance, there is no exploration of how agent performance varies with the number of abstract states.\n\nThirdly, the analysis does not explore some existing approaches that are closely related. For example, as the authors note, Ramesh et al. (IJCAI 2019) propose a similar abstraction of the environment using the successor representation, which would be an informative baseline. Approaches based on graph cuts/clustering would also be relevant and informative. Some of these methods may not scale as well as the proposed approach but it would still be useful to see their similarities/differences and relative strengths/weaknesses explored. \n\n-- How the approach would fare in stochastic environments is not discussed or explored. \n\n-- Computational complexity of the approach is not discussed or explored.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Q0LM-ME5C4", "reviewer": "Reviewer_C2ny", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper outlines an approach to use successor representations to drive a discrete state space abstraction. The abstract states are clusters in successor space, so \"nearby\" states have similar successors. The paper also contributes a way to utilize the abstraction learned to solve tasks efficiently by interpreting transitioning between abstract states as options, and outlines an algorithm to jointly learn the successor representations, the abstract representation and the option policies.", "summary_of_the_review": "This is a good quality paper, cleanly written and justified with appropriate experimentation and I recommend acceptance to ICLR.", "strength_and_weaknesses": "This is a well written paper which clearly describes its motivations, contributions as well as limitations. The method is theoretically grounded and seems sound. The approach is novel as far as I am aware and cleanly described. The experiments are well thought-out and appropriate comparisons are made to prior approaches.\nThe environments are a bit simple, but given that prior approaches are less effective/noisy on them, that is justified.\nMore quantitative results could have been included for different exploration policies for learning the success features/abstractions.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "0HZSOtk5ln0", "reviewer": "Reviewer_TM9s", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to learn a successor representation and use it to cluster the states. The clusters are then treated as nodes of a graph and an (option) policy is trained to navigate the graph. The graph can be used in either a goal-oriented setting by searching; or a reward maximization setting with a lazy random walk.", "summary_of_the_review": "This paper is an empirical one where a lot of design choices are based on the authors' intuition. However, the paper didn't provide strong empirical evidence that the method they proposed actually works in tasks with practical value. All the tasks are quite simple (2d navigation and 2d arm) and working on them is more of a proof of concept. There could be so many implicit hypotheses that the method relies on if they can only work on tasks with this low degree of freedom. Even for these toy tasks, it's not clear whether the method has any advantages over well-established control/RL methods due to the lack of baselines.\nI think this paper is not ready for acceptance for ICLR.", "strength_and_weaknesses": "Strength:\n1. The idea of learning a graph and using it for hierarchical decision-making is interesting on a high level.\n\nWeaknesses:\n1. Environment of all the tasks is of very low degree of freedom (Dof=2), and the optimal policy is very simple. It's unclear whether the method can be applied to tasks with practical value. \n2. The motivation of a lot of the novel designs (the successor representation loss in eq (2), lazy random walk for reward maximization) is not well-justified and seems like can cause problems in a general setting.\n3. The baselines this method is comparing to in section 6.2 are within their framework. It's more like ablation of representation learning component of DSAA. No proper offline/online, model-based and model-free RL methods are compared to the proposed method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject