Novel Exploration via Orthogonality
Authors: Andreas Theophilou
Özgür Şimşek
Venue: NeurIPS 2025 poster ()
Keywords: Laplacian
Novelty
Reinforcement Learning
Exploration
Eigenvectors
Spectral Methods
Primary area: reinforcement_learning
TL;DR: We use Laplacian representation to improve exploration for reinforcement learning agents.

Abstract: Efficient exploration remains one of the most important open problems in reinforcement learning. Discovering novel states or transitions requires policies that efficiently direct the agent away from the regions of the state space that are already well explored. We introduce Novel Exploration via Orthogonality (NEO), an approach that automatically uncovers not only which regions of the environment are novel but also how to reach them by leveraging Laplacian representations. NEO uses the eigenvectors of a modified graph Laplacian to induce gradient flows from states that are frequently visited (less novel) to states that are seldom visited (more novel). We show that NEO's modified  Laplacian yields eigenvectors whose extreme values align with the most novel regions of the state space. We provide bounds for the eigenvalues of the modified Laplacian; and we show that the smoothest eigenvectors with real eigenvalues below certain thresholds provide guaranteed gradients to novel states for both undirected and directed graphs. In an empirical evaluation in online, incremental settings, NEO outperformed related state-of-the-art approaches, including eigen-options and cover options, in a large collection of undirected and directed environments with varying connectivity structures.

Novel Exploration via Orthogonality
Andreas Theophilou University of Bath United Kingdom aj t800bath. ac. uk
Özgür Şimşek University of Bath United Kingdom
o. simsek@bath ac. uk
Abstract
Efficient exploration remains one of the most important open problems in rein- forcement learning. Discovering novel states or transitions requires policies that efficiently direct the agent away from the regions of the state space that are already well explored. We introduce Novel Exploration via Orthogomality (NEO), an ap- proach that automatically uncovers not only which regions of the environment are novel but also how to reach them by leveraging Laplacian representations. NEO uses the cigenvectors of a modified graph Laplacian to induce gradient flows from states that frequently visited (less novel) to states that are seldom visited (more novel). We show that NEO's modified Laplacian yields eigenvectors whose extreme values align with the most novel regions of the state space. We provide bounds for the eigenvalues eigenvectors with real eigenvalues below certain thresholds provide guaranteed gradients to novel states for both undirected and directed graphs. an empirical evaluation in online, incremental settings, NEO outperformed related state-of-the- art approaches, including eigen-options and cover options, in a large collection undirected and directed environments with varying connectivity structures.
the modified Laplacian; and we show that the smoothest
Introduction
Temporal abstraction has been widely studied as an approach efficient exploration, which remains one of the key research challenges in reinforcement learning. State of the art methods include eigen-options [ 2 and cover time options 3. In symmetric settings, both of these methods can produce policies that push the agent toward the far reaches of the state space. However, such regions may already be heavily visited, and policies that push the agent naively to far away reaches of the environment are not always effective explorers.
An alternative approach is count-based exploration through pseudo-rewards. for example, by giving the agent a novelty bonus proportional to 1 for having visited state-action pair times. Some algorithms that take this approach come with theoretical guarantees [4. However, these algorithms do not provide explicit gradient guidance to the agent. Rather than providing explicit policies for exploration, they rely primitive actions and standard reinforcement update rules, such as Qavalue learning, to propagate their intrinsic rewards, which can introduce lag exploration until the agent's value estimates have sufficiently propogated.
This approach addresses novelty
natural alternative to construct policies that explicitly drive the agent toward the most novel states [8] With access to an oracle solver for shortest paths in the transition graph, in symmetric settings, such policies can guarantee reaching a maximally novel state within a given horizon. However, this approach focuses exploration very narrowly on a single target, rather than diversifying across multiple novel regions.
We introduce Novel Exploration via Orthogonality (NEO), method that maintains the strengths of prior approaches whilst addressing their weaknesses. As with related spectral methods, NEO uses the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Laplacian eigenvector's smooth and orthogonal property to encourage exploration towards distinct regions of the state space. Unlike prior methods, NEO introduces gradient guarantees and focuses the exploration towards regions that are novel.
Importantly, NEO stands out by providing Laplacian-based policies in directed settings. Previous Laplacian approaches assume an undirected transition graph, even though many real-world environ- ments are inherently directed. Recent work has proposed using the polar decomposition of a transition matrix to recover real eigenvalues to obtain eigen-options in the directed setting [9]; however, this approach uses a symmetric, Hermitian matrix, which cannot provide directed gradient flows beyond the symmetric graph obtained in the construction. Moreover, eigen-options in directed settings by used only as a baseline; it has not been shown in evaluations to perform desirably (9] By careful construction, we obtain eigenvectors with gradient guarantees in strongly connected directed graphs for any eigenvector with an associated real eigenvalue below given value. Conceptually, as we create a modified Laplacian and take its eigenvectors, we effectively convert novelty to energy where the most novel states dominate the contributions to the inner product (u, v) = Σ, u and are the highest energy states of the smoothest Laplacian eigenvectors with real eigenvalues below a novelty-based threshold.
polar decomposition
We provide experimental results in a wide variety of environments, both directed and undirected, that illustrate the approach and its effectiveness. In online, incremental settings, NEO outperformed related state-of-the art approaches, including eigen- oigenopptions and cover options, in a large collection of undirected and directed domains with varying connectivity structures I
2 Preliminaries
A finite Markov decision process (MDP) is 5-tuple (S, T, R, 7), where S is set of states, A a set of actions, T(s, a, s') E [0. 1] the probability of transitioning to state s' upon taking action a in state s. R(s, a, s') the expected reward for that transition, and y [0, 1] the discount factor. At decision stage t, 2 0, the agent is in state E S, selects action az E A. and transitions to state 8141, receiving reward 1++1- A policy T(s, a) gives the probability of selecting action a when in
E.EA a) EvES a(s,a, s') [R(s, a.)) + y (* is the expected discounted sum of future rewards when following policy n from state 8. An optimal policy is one that maximizes V (s) for every state 8 E S.
state The value function (*(s)
We refer to the actions of an MDP as primitive actions and represent temporally-extended actions using options 1T [1]. An option is a triple (o, 3o), where Io S S is the set of states in which the option can be initiated, n. is the policy followed during option execution, and 13 S - [0, 1] is the termination condition, expressing the probability of termination in a given state.
To,
Associated with an MDP (S,A, R, 7), we define directed graph G (V.E). where V S is the set of vertices and F is the set of edges, with (s, E F. iff Ea E A such that T(x, 8') 0. Given this transition graph, we define adjacency matrix A, where Aij 1 if (i.j) E E and Ag
otherwise, and random walk transition matrix P. where P.j out-degree of a node deg+ (1) = -, Asg.
with deg* denoting the
deg (t)
The Rayleigh quotient of matrix M E Caxn at vector x E C" [0} is the scalar R(M; x) = x" Mx where x* is the conjugate transpose of x. We use À to denote the eigenvalues and f the eigenvectors. If M is Hermitian (M = M*), then x(M;x) R for all o O. and Amin (M) minx R( M x), Xmax = maxxy0 X(M;)), with the extrema attained exactly at the corresponding eigenvectors f of M. For a complex number, we use R to refer the real part and S to refer to the imaginary part.
X'X
3 Source Laplacian
We start with defining source Laplacian Lę by adding non- non-negative diagonal weights to the random- walk Laplaciinn I = T - P, thereby concentrating energy selected nodes. Let G (V, F) be a directed, strongly connected graph of n nodes, with row-stochastic transition matrix P =
All code is available at htttpgg///gthhib.ccc///aeeeeeeee

---

(Pt)) Pij 2 0, P.j - (Vi). Let denote the identity matrix. Introduce nonnegative weights < (4:)=11 and define x matrix I, with F. < and all other entries zero. Define Adding I' increases the diagonal entries and, in eigenvectors of Le, pulls the eigenvector value at weighted nodes toward zero, raising the relative prominence of less weighted nodes where energy gets concentrated. A node with Çi = is a source node. A node with Ç > is sink node. The Rayleigh quotient of source Laplacian Lg for any C (10 is:
Lc = 1++
x' L2L R(x)
x² (I + F x Pæ
El= Ci) D2
Ei 24 Pays
xx
x²x
where x; is the complex conjugate of xy- If the graph is symmetrie, the Rayleigh quotient can be expressed as:
Poyl: 1.n-xxy z,)² + Es
2
R(x)=
x: L x x
i.j
Σ m
This is the standard Rayleigh quotient for symmetric matrix L = - P with the additional term Σ, <,a which is the added squared smoothness error contributions Ç1(x; - 0)2 between the node values x; and the zeros, weighted by Ç..
Below, we present three theorems. Theorem 3.1, we prove lower bound for the eigenvalues of the source Laplacian and an upper bound for its smoothest eigenvalue. In Theorem 3.2, we show that, for certain eigenvalues, the maximum of the associated eigenvector is attained at a source node. In Theorem 3.3, for the source Laplacian with I' weighted by visitation values, we prove that, certain eigenvectors (those with associated eigenvalues lower than the maximum visitation value) give us guaranteed gradients (and thus paths) from nodes with higher visitation values to nodes with lower visitation values.
Theorem 3.1 (Bounds for the eigenvalues of the source Laplacian 1-= = (T+ P). Suppose k nodes are sources (C: = 0) and n k are sinks, each with uniform weight > 0 (that is, G for all sinks). Then, < R(1) < μ., and the upper bound for the smoothest eigenvalue is p. If all sources are replaced with weight a, where μ > O, then a < R(1) ju, and the lower bound for the smoothest eigenvalue a. all G = μ. then R(1) = μ., and the smoothest eigenvalue is μ.
Proof. R(1)= = E G. In the standard case, with i sources and n sinks, & entries are zero and n n-k entries equal Jl, and E. (n-k)y,. Consequently, R(1) (n-k))/n n (1-k/ k/n)),,, which implies 0 < R(1) < μ. In the a-weighted variant, Σe Se = ka + (n - k)j, so R(1) = (n- k)a combination of and μa, hence a < R(1) μ.. In the uniform case, Σ, Ci n/44, giving R(1) n.
Theorem 3.2 (Maximality (in magnitude) of the eigenvector at sources). Given source Laplacian Le = (I +') - P. assume f = Af with real eigenvalue < min.ç,>0 Çt, that is, the eigenvalue less than the minimum non-zero weight in Ç. Then the element of eigenvector ff with the highest absolute value, [fs], must be a source node (Ç. = 0).
Proof. From T = Aʃ and -== = I - P, we have (T+ P) Af- Then for the zh row (corresponding to node i), after rearranging, we get (1 Gi A)ʃf E, Pujfz. which yields:
f:= I+ ---12-X-0 EPuh E
Taking absolute values at both sides of the equation, we obtain Ifal 1 E, Pasfi node is sink node, then & > X, and 1 + C A/ > 1, and so
If the 2th
[fl <
1
Σ
Pulfal max 1s3b.
1 4 X
3

---

implying that, for sink node i, Ifsl cannot be maximum entry of f in magnitude. Therefore, maximality must be obtained at source node.
Theorem 3.3 (Novelty path via visit counts). Let G be strongly connected graph, and N(i) visitation value of node i. Define L = (I +)+ P with I = (i) E R20- For any eigenvalue and associated eigenvector f (right eigenvector if Lę asymmetric) where N() R())
there exists directed path vp + U + + us such that [opl < [ < (va) (A))
[ and
Proof. Following the same reasoning for the tt entry of Lef Af as in Equation have (1 N(1) =, P.jfz Therefore,
f 1+)(1) - E
If (1) > R(AA, then
(+) - = (1+ - R(A) -V
V(1+ N(1) +(()))+++ +
2 I+N(1) R(A) > 1.
Therefore,
lftl = [1+ N(1) A Posl < E
implying E, Pullll [ft]. Thus some neighbor j has |Sl
[sa.- Iterating yields strictly
increasing chain in [f], terminating at e with no neighbor with a larger magnitude, forcing (1) - A < 1 and ((x)) < R(A).
Remark 3.1. Because Theorem 3.3 uses only the magnitudes [fol. any complex phase of f is irrelevant to the strict-inequality relations among [f, J, i O,....k
In the undirected setting, Lę is Hermitian and all its eigenvalues and eigenvectors real. Conse- quently, one may simply take the eigenvectors corresponding to the & smallest eigenvalues, knowing that each of these smoothest eigenvectors will define orthogonal gradient field that carries mass from states with lower visitation values to states with higher visitation values, as long as the corre- sponding eigenvalue À is less than the maximum visitation value. When is directed, I.ç becomes non-Hermitian, and complex eigenvalues (and eigenvectors) can appear. Nevertheless, any eigenvalue with RR) below the maximum visitation value still induces guarantced gradient from nodes with higher visitation values to nodes with lower visitation values.
4 Novel Exploration via Orthogonality (NEO)
We now use the smoothest eigenvectors of the source Laplacian I.g to define multi-step exploration policies in the form of options. We call the proposed approach Novel Exploration via Orthogonality, or NEO, and outline it in pseudocode Algorithm 1.
At each iteration of the algorithm, we start by following the agent's policy for H steps, recording every transition as assemble (or update) empirical graph with transition matrix P and to accumulate raw visitation counts (ss) ((s for each state s encountered during the roll out. Raw counts can vary wildly between instantiations: we therefore transform them via scaling function F: R E. using two parameters: 5 > 0 k >> O. Specifically,
1/k
F(N(s))
N(s) MAXIES N(O)
where the denominator maxies N(i) ensures that the maximum scaled count prior to being multiplied by 8 less than or equal the exponent 1 l/: compresses their dynamic range, and the multiplication with further shrinks increases them. In Appendix B, we present results obtained by varying d and

---

k. For all results presented in the main paper, we use d = 0.5 and & = 64. Using the scaled visitation counts Ç; (i)), i E we define an n x matrix r, with T = ç and all other entries set to zero, and another
matrix L = T + - P. the source Laplacian.
We then compute the Z smoothest eigenvectors of T.ç, those associated with its Z smallest real cigenvalues. For every eigenvalue À < 6, the associated eigenvector f defines a gradient that naturally points away from states that are heavily visited toward those that less explored.
We instantiate one option per eigenvector. We use fo to denote the eigenvector that corresponds to option This option can be initiated in any state. The option policy moves the agent to the neighboring state with the largest magnitude of the corresponding eigenvector, If The option terminates with probability when the agent reaches local peak of I magnitude of the eigenvector exceeds or equals that of all its immediate neighbors), with probability zero elsewhere.
(that is, state where the
Algorithm NEO
1: Input: update horizon H, option count Z, scaling function F // set of options I/ set of states
2: 0
3: S =
4: loop
5:
Execute agent policy for H steps
6:
Update state set S. graph G, transition matrix P. and visitation counts
7: Le = I+ - P, where l = ((N
8:
Compute eigenpairs {(A.: fo)) of Lic, sorted by ascending A
9:
for to Z do
10:
I, S
initiation set // termination condition // option policy
Bo(s) 1 iff Vs' (s | S |
12:
[a(s) = the action that leads to next state s' that maximises
[
(Io, Toy 3o)
14:
O + Ouo
end for
16: end loop
In Figure [ illustrate the componentwise magnitude for eigenvectors of the source Laplacian in some directed and undirected domains. Plots (a) and (b) illustrate how the eigenvectors of the source Laplacian capture directed connectivity. In plot (a), we show 20-node directed cycle, with one source (C- = 0: the node in the darkest shade of green) and all other nodes as equal sinks (C = 0.1), yielding smooth eigenvector that increases monotonically around the circle. In plot (b), we show directed four-room grid with one-way doorways. Setting the top left corner as the source (C = 0) and all other states as sinks (S- = 0.1) produces an eigenvector whose gradient reflects directed distance from sinks to the source.
Plots (c) and (d) show how derive weights for I from visitation counts in directed four rooms and in a maze environment, respectively. In directed four rooms, the agent performed a random walk of 100 steps, starting at the top left corner; this was repeated for 100 trials. In the maze, the agent performed a random walk of 10000 steps, starting at the bottom left corner; this was repeated for 500 trials. In both domains, visitation counts were scaled by their maximum, raised to the power of to compress their dynamic range, and multiplied by d = 0.5. In directed four-rooms, one state was never visited, whereas all states in the maze received some visitation (minimum ('(N()) 0.475).
Using the scaled visitation counts F-N(-)) to add to the diagonals of T, plots (e)-(h) display componentwise magnitude of the first four eigenvectors (scaled by vr. for visualization) of the source Laplacian with novelty weighting for in directed four rooms; plots (i)-(I show the same construction in the maze domain. We measured the cosine similarity between eigenvectors in directed four rooms (the eigenvectors displayed in plots (e)-(h)); the maximum value observed was 0.001. Orthogonality leads to distinct novel regions being high in magnitude across the eigenvector values. Notice that the smallest eigenvalue in plots (c) and (i) align with the theoretical lower and upper bounds by the minimum diagonal value of I. We have a minimum (()) of in plot (c) and 0.475 in plot (d) with a maximum F (.)( of 0.5 in both, resulting in eigenvalues of x 0.1 in plot (e) and 0.48 in plot (i).
5

---

15
1iil
Visiation
Vidution
M4
1/4 (Aa 0.3343)
Ifa (Aa 0.3714)
(Ar Re 0.1861)
(Ag de 0.02457)
(4)
|/.1 (Ag ou 0.4800
If (A, so 0.4506)
(Au = 0.4825)
(Aa Ps 0.6861)
m
i
Figure I: Smoothest eigenvector LC in (a) directed-cycle, (b) directed four rooms. Visitation- sink weights in (c) directed four-rooms, (d) large maze. The first four eigenvectors of the source Laplacian Lg (scaled by tf for visualization) in (e-h) directed four rooms, and (i-I) large maze. Please refer to Figure 2 for visual depiction of these domains.
5 Related Work
demonstrated that the first eigenvector of an undirected graph Laplacian provides an approximate shortest-path solution via single sink node, inspiring the spectral method proposed here. Earlier related works include eigen-options 13 2) which use eigenvectors of normalized Laplacian for options policies, as well as proto value functions 14 which use the same eigenvec- tor construction for representation learning and efficient value estimation. Cover options (3) build on eigen-options, applying solely the fielder vector recursively. Diffusson options [9] use eigenvectors of the Laplacian to find diffusely separated option termination states; however, this method is not currently applicable in the online setting. The successor representation [16] has been shown to be closely related to the graph Laplacian [17]. Another set of closely related graph-basee bashb methods include sub-goal discovery via betweenness [18), graph cuts [19 20), graph components [2I] bridge centrality
Steinberger 12]
[22] stability centrality (23). graph clustering [24 25). relative novelty [7]. and modularity
maximization [26] Also related are methods for extending novelty counts to the deep reinforcement
learning setting 66
29 and learning novelty based distances (0
Empirical Evaluation
we present visual depiction of the domains used in our analysis. Those under 1000 states include directed four rooms, a gridworld with four rooms connected via one-way hallway states, Rubik's cube end game, the undirected subgraph of the 2 x Rubik's cube containing
In Figure

---

the states that are within 3 moves of the solved state, and the classic tower of Hanoi puzzle. At roughly 2500 states is the office, an undirected environment challenging to previous spectral- ppestral-based exploration methods [26]. Larger still are large maze and hex, each with approximately 5500 states. In addition to these undirected versions, we created and experimented on directed versions of large maze and hex by adding single directed edge between the two most distant states. Our largest domains are a directed New York City (NYC) street graph consisting of 10000 nodes and the directed torus domain. In directed torus, the red walls on the right side wrap in one-way direction (from right to left) to the walls on the left side, and the blue walls at the top wrap one-way direction (top bottom) the walls at the bottom. This domain challenging alternative to a standard torus, allowing us to assess how agents navigate when traversing any of a large number of directed edges that can preclude finding returning paths.
constructed
more
We use Q-learning with step size a = 0.4, discount rate 7 0.99, an e-greedy policy with e = 0.1, augmented with growing library of temporally extended actions in the form of options. The initial Q values are set to 0 for primitive actions and -0.00001 for options, ensuring that the agent policy initially favors primitives unless exploration explicitly invokes an option. When the e-greedy policy takes an exploration step, with probability initp the agent chooses a random option, otherwise random primitive action. We fix initp at 0.1 for reward based evaluations in Figure 3 we evaluate the impact of the initp parameter in Figure 4 An option can be initiated in any state that was part of the graph used when the option was constructed (in other states, there would be no constructed option policy). Each transition triggers the usual one-step Q-lcarning update (s,aa) a) < (1 a as)(ss a) + a + y max, Q(s', ad) ((s, a)]. Additionally, at the end of an episode, the entire episode's ss transitions are replayed in reverse order, with the same Q-learning update accelerate reward propagation in our sparse-reward reward task. Option values learned using SMDP
Q-lcarning backups: Qss.o) + (1-a) Q(s,0) +
E 7 re+s+1 + Y max Q Q( d')
where is the state in which option was initiated, option duration until termination, and r++s+1 are the rewards accrued while executing option o.
In all domains, there is single goal state. Upon reaching the goal state, the agent receives a reward of +100 and the episode terminates. All other transitions give a reward of O. We use an adaptive episode horizon: 500 steps for domains under 1000 states, 1000 steps for domains with 501-3000 states, and otherwise the number of states in the domain. For each evaluation agent instance, a goal state is randomly chosen and the farthest state from the goal state is set be the start state for all runs for the agent instance. For each method, we run 20 agent instances; we use a random seed (equal to run number) before selecting goal and start states, ensuring all start and goal states are the same across compared agents.
Directed Four Rooms
Office
Hex
Large Maze
ALL
Rubiks Cube
Tower of Hanoi
Directed NYC Graph
Directed torus
Figure 2: visual depiction of the eight domains used in the empirical analysis.
7

---

Four Rooms
Four Rooms (Directed)
Rubiks Cube
Tower Hamoi
Noword
MBC
RED
pands
Epsch
Epoch
Ezech
Epoch
[c)
Office
Hex
Large Maze
Large Maze (Directed)
Epr
Eam
Epoch
Epach
(e)
Hex Hex: (Uirected)
Torus (Diected]
NYC (Drretedd)
140
MCC
of haamooouf
Epoch
Epoct
Spoch
(1)
Figure 3: Comparative sparse reward empirical evaluation of learning agents with different option discovery methods across a set of domains.
Options are discovered online every I decision stages, with H set to five times the number of nodes in the domain's 's full transition graph. We generate four new options per update, capping the total stored options at 64 and discarding the oldest four options when capacity is exceeded and replacing them with the most recent four options. Each option policy is defined by ascending a representation until reaching local maximum: for eigen-options, the representation is an eigenvector of the graph Laplacian; for cover-options, it is the Fiedler vector over graph nodes; for the shortest-path-nover options, it is the shortest path distance the most novel node in the agent's working graph; and for NEO options, it is the magnitude of the eigenvectors described previously in Theorem 3.3. The eigenvectors can also be taken intrinsic rewards for option policies instead of direct solutions. In Appendix C, we include the results for eigen-options and cover-options solved with policy iteration. In directed domains, the poompsscoo variant of eigen-options are applied. We cannot use cover options in directed domains because they rely on the construction of Fiedler vectors.
[8]
Every 2000 steps, which we define evaluation episode where no exploration actions are taken (e = 0). We plot the evaluation results with 2o error width. As bascline, we also include Q-learning agent using only primitive action, receiving intrinsic novelty bonus 3/ ///vnn //n a), with 8 = 0.01.
epoch, we freeze exploration and run independent
The learning curves are shown in Figure 3 Plots (a) - (d) show the learning curves for our simplest benchmark domains: four rooms (undirected and directed), Rubik's cube end game, and the tower of Hanoi. All ppseed agents reach the maximum reward relatively quickly, with the exception of the shortest-patte notte-olltttt method, which exhibits slower learning the tower of Hanoi.
8

---

Plots (c) (g) compare performance on three undirected domains: office, hex, and large maze. Here the proposed method NEO shows a clear advantage over the alternative approaches. By the end of training, NEO agents achieve the maximum reward of 100 on average, while the other methods fail to achieve higher than 40. We also include a variant of NEO that uses only the first (i.e., smoothest) eigenvector, yielding a single option per update interval, which outperforms the related methods. However, it is evident from the evaluations that leveraging multiple eigenvectors provides additional learning benefits beyond this single eigenvector baseline.
In plots (h) - (k), we present results in directed domains. As in the undirected setting, both NEO variants outperform the alternative methods across all directed tasks. The agent's 's state transition graphs remained weakly connected throughout most of learning. and we obtained no complex eigenvalues in the construction of any option policy for NEO, with all 4 smoothest eigenvalues computed every H update iterations being real valued. We hypothesized that the presence of sink states stabilizes the eigenvalues and makes it more likely that they are real valued. In Appendix E, we provide theoretical bound showing that the imaginary part of the eigenvalue is notably impacted by the sink weights and present empirical results. For the NYC directed domain, eigen-options could not be computed because the solver would crash. We suspect this issue arises from the interaction between the polar decomposition method and initially weakly connected graphs, which may impair numerical stability during option computation.
In Figure we present the number of unique nodes visited by each method, with various values of the option initialization probability init p. Lower initialization probabilities consistently improve coverage for all methods. However, only NEO approaches full coverage in hex and large maze. These are the largest symmetric domains where is possible to compare all methods. In these domains, NEO achieves higher unique-node count during evaluations, roughly twice that of the competing approaches.
Overall, these evaluations demonstrate that NEO achieves or surpasses state-of-the-ar performance in both undirected and directed environments, in terms of exploration and, by extension, learning.
One boundary of the Fiedler vector tends to sit in a well-visited region. Eigen-options and cover options include the Fiedler vector among their option sets. To understand the performance gap between these methods and NEO, we analyze how the signed option pair, corresponding to eigenvectors f and f", can undo progress by steering the agent back to states that relatively well
Large Maze
Large Mare
Large Moce
Large Maze
Mode Couste
Car 100e-20
Can lice 4.
Cos Coe
3tupetinoo well 10
welh
fpars (c)
Eooch
(a)
(d)
Mode Courte
Nods Courta
Epoch
Epech
(+)
(c)
(b)
Figure 4: Comparative initialization probability and node count evaluations of learning agents with different option discovery methods across a set of domains.

---

explored. For this analysis, we use the two largest symmetric domains where Fiedler vectors can be computed, hex and large maze.
Consider an agent that begins near a corner of the full graph and builds the graph incrementally. That corner typically becomes the region that is the most connected and the most frequently visited. Placing one boundary (say b1. an extremum of the Fiedler vector f) in this region tends to be part of
the first non- con-trivial solution of the Rayleigh quotient R(f) = Ein n: (fu-
because the dense local connectivity allows f to taper off gradually, keeping each edge difference (fu. fu) and thus the numerator small. If the second boundary were nearby, neighbouring nodes would carry opposite extreme values, the numerator would spike, and the quotient would rise. Minimising the quotient therefore pushes the second boundary to a geometrically far away state, such as another corner of the graph, rarely visited.
ff
After 250K steps, we freeze the exploration graph and visitation counts NC)., compute eigen-options, and extract the Fiedler vector f. Let by and by be the two boundary states (the extrema of f). and define blow = arg (in(N((b) Nbb))) and bhigh == arg max (N(b) (br), Nb2)). We initialize the agent at blow and execute the Fiedler-vector option that follows the increasing f f-gradient, moving toward the opposite boundary until the gradient stalls at a local or global maximum. Our aim is to assess whether one of the pair tends to undo progress. Table shows the visitation counts N (-) at Fiedler vector boundaries blow and bnigh. the difference, and the visitation counts at the option termination state. For both domains, one of the signed options lifts the agent from relatively novel states to frequently visited states (c.g.. mean 68.5 + 822.6, median 14.5 - 745.0 in hex). Because the two options are chosen with the same probability, the option that drives the agent back to the high- vighttiittttion boundary can directly undo the progress made by its counterpart that moves toward the low-visitation boundary.
Table 1: Visitation count statistics in 20 runs.
N
(bnigh)
(bnigh)
N (bbow
(terminnatio))
Domain
Mean
Median
Mean
Median
Mean
Median
Mean
Median
Large Maze
129.8
39.0
1355.1
1070.5
1225.3 890.5
952.5
985.6
638.0
Hex
68.5
14.5
958.9
503.5
467.0
822.6
745.0
7 Conclusion and Future Work
We presented a principled approach for generating exploration options via proposed source Lapla- cian, leveraging theoretical insights and spectral graph properties to guide exploration to novel parts of the state space. The proposed method is shown drive agents toward novel regions, improving learning performance across a range of challenging domains compared to the existing state-of-the-art The approach shown be applicable both undirected and directed environments, demonstrating versatility.
Although the theoretical and empirical results presented in this paper center on using state novelty as the driving signal, the proposed framework is general and is not restricted to the use of novelty alone. In fact, any real-valued state functions could be plugged in. Future work can, for instance, replace or augment novelty with expected reward, reward prediction error, or competence signals. We discuss the future extension to symmetric Hilbert spaces in Appendix D.
Recent approaches to approximate the cigenvector of the Laplacian 31 32 33 and commute times [34] via these cigenvectors provide foundation for future work in extending Laplacian-basee option discovery methods to the large and continuous setting.
A current limitation is obtaining eigenvectors of the source Laplacian Lę in Hilbert space as done in the symmetric case of the random walk Laplacian [33]. This limitation currently exists for all asymmetric Laplacians, with potentially complex eigenvalues, complex eigenvectors, and non- Euclidean inner products. Another limitation is that exploration policies are currently being learned for particular environment, one at a time. Future work can explore how these policies can be learnt in a general way, to be used effectively in other parts of the environment or even in new environments, drawing inspiration from approaches to temporal abstraction that focus on generalisation (35].
10

---

Acknowledgements
We would like thank the members of the Bath Reinforcement Learning Laboratory for their comments and useful suggestions.
References
[1] Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Conference Learning Representations, 2018.
[2] Marlos C Machado, Andre Barreto, Doina Precup, and Michael Bowling. Temporal abstraction in reinforcement learning with the successor representation. Journal of Machine Learning Research, 24(80): 69, 2023.
[3] Yuu Jinnai, Jee Won Park, David Abel, and George Konidaris. Discovering options for explo- ration by minimizing cover time. In International Conference on Machine Learning, pages 31 3130-3139. PMLR, 2019.
[4] 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 1331, 2008.
[5] Kai Yang. Jian Tao, Jiafei Lyu, and Xiu Li. Exploration and anti-exploration with distributional random network distillation. Proceedings of the 41st International Conference on Machine Learning, pages 56397-56421, 2024.
[6] Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. #Exploration: A study of count-based exploration for deep reinforcement learning. Advances Neural Information Processing Systems, 30, 2017.
[7] Özgür Şimşek and Andrew G Barto. Using relative novelty to identify useful temporal abstrac- tions in reinforcement learning. In Proceedings of the Twenty-First International Conference Machine Learning, page 95, 2004.
[8] Martin Stolle and Doina Precup. Learning options in reinforcement learning. In International Symposium on Abstraction, Reformulation, and Approximation, pages 212-223. Springer, 2002.
[9] Amitay Bar, Ronen Talmon, and Ron Meir. Option discovery in the absence of rewards with manifold analysis. International Conference on Machine Learning, pages 664-674. PMLR, 2020.
[10] Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1- 2):181-211, 1999.
[11] Doina Precup. Temporal abstraction in reinforcement learning. University of Massachusetts Amherst, 2000.
[12] Stefan Steinerberger. spectral approach to the shortest path problem. Linear Algebra and its Applications, 620: 82-200, 2021.
[13] Martin Klissarov and Marlos C Machado. Deep Laplacian-based options for temporally- extended exploration. In International Conference on Machine Learning, pages 17198-17217. PMLR, 2023.
[14] Sridhar Mahadevan. Proto-value functions: Developmental reinforcement learning. In Pro- ceedings of the Twenty-Second International Conference Machine Learning, pages 553-560, 2005.
[15] Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A Laplacian framework for learning representation and control Markov decision processes. Journal of Machine Learning Research, 8(10), 2007.

---

[16] Peter Dayan. Improving generalization for temporal difference learning: The successor repre- sentation. Neural Computation, 5(4):613-624, 1993.
[17] Rahul Ramesh, Manan Tomar, and Balaraman Ravindran. Successor options: An option discovery framework for reinforcement learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3304-3310, 2019.
[18] Özgür Şimgek and Andrew Barto. Skill characterization based on betweenness. Advances in Neural Information Processing Systems, 21, 2008.
[19] Özgür Şimsek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforce- ment learning by local graph partitioning. In Proceedings of the Twenty-Second International Conference on Machine Learning, pages 816-823, 2005.
[20] Ishai Menache, Shie Mannor, and Nahum Shimkin. Q-cut dynamic discovery of sub-goals in reinforcement learning. In European Conference on Machine Learning, pages 295-306. Springer, 2002.
[21] Seyed Jalal Kazemitabar and Hamid Beigy. Using strongly connected components basis for autonomous skill acquisition in reinforcement learning. In Wen Yu, Haibo He, and Nian Zhang, editors, Advances in Neural Networks - ISNN 2009, pages 794-803, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
[22] Parham Moradi, Mohammad Ebrahim Shiri, and Negin Entezari. Automatic skill acquisition in reinforcement learning agents using connection bridge centrality. In Tai-hoon Kim, Thanos Vasi- lakos, Kouichi Sakurai, Yang Xiao, Gansen Zhao, and Dominik Šlęzak, editors, Communication and Networking, pages 51 62, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
[23] Ali Ajdari Rad, Martin Hasler, and Parham Moradi. Automatic skill acquisition in reinforcement learning using connection graph stability centrality. In Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pages 697-700, 2010.
[24] Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the Twenty- Perst--First International Conference on Machine Learning, page 71, 2004.
[25] Negin Entezari, Mohammad Ebrahim Shiri, and Parham Moradi. A local graph clustering algo- rithm for discovering subgoals in reinforcement learning. In Tai-hoon Kim. Thanos Vasilakos, Kouichi Sakurai, Yang Xiao, Gansen Zhao, and Dominik Šlęzak, editors, Communication and Networking, pages 41-50, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg.
[26] Joshua Evans and Özgür Şimşek. Creating multi-level skill hierarchies in reinforcement learning. Advances in Neural Information Processing Systems, 36:48472-4888 484444, 2023.
[27] 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-1477 2016.
[28] Tianjun Zhang, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph Gonzalez, and Yuandong Tian. Noveld: A simple yet effective exploration criterion. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 25217-25230. Curran Associates, Inc., 2021.
[29] Sam Lobel, Akhil Bagaria, and George Konidaris. Flipping coins to estimate pseudocounts for exploration in reinforcement learning. In International Conference on Machine Learning, pages 22594-22613. PMLR, 2023.
[30] Yuhua Jiang, Qihan Liu, Yiqin Yang, Xiaoteng Ma, Dianyu Zhong, Hao Hu, Jun Yang, Bin Liang, Bo XU, Chongjie Zhang, and Qianchuan Zhao. Episodic novelty through temporal distance. In The Thirteenth International Conference on Learning Representations, 2025.
[31] Yifan Wu, George Tucker, and Ofir Nachum. The Laplacian in RL:: Learning representations with efficient approximations, In International Conference on Learning Representations, 2019.
12

---

[32] Kaixin Wang, Kuangqi Zhou, Qixin Zhang, Jie Shao, Bryan Hooi, and Jiashi Feng. Towards better Laplacian representation reinforcement learning with generalized graph drawing. In International Conference on Machine Learning, pages 11003-11012. PMLR, 2021.
[33] Diego Gomez, Michael Bowling, and Marlos C. Machado. Proper laplacian representation learning. In The Twelfth International Conference on Learning Representations, 2024.
[34] Kaixin Wang, Kuangqi Zhou, Jiashi Feng, Bryan Hooi, and Xinchao Wang. Reachability-awan aware laplacian representation in reinforcement learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
[35] Thomas P Cannon and Özgür Şimşek. Accelerating task generalisation with multi-level skill hierarchies. In The Thirteenth International Conference on Learning Representations, 2025.
[36] MKG Kruse, JM Conroy, and HG Miller. arXiv:/1/2.0290 //2.0029, 2011.
The Rayleigh quotient.
arXiv preprint
[37] Fuzhen Zhang, editor. The Schur complement and its applications. Springer Science & Business Media, 2005.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: Yes
Justification: In the paper we do provide evidence that the proposed method (NEO) outper- forms related state of the art methods, that we get gradient guarantees and bounds for method.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: Yes
Justification: We discuss the limitation in the supplementary material, particularly on the problem of obtaining directed eigenvectors in large continuous spaces.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
14

---

Answer: Yes
Justification: We provide the assumptions and complete, correct proofs, further details of related proofs given are in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: Yes
Justification: We provide the details needed to re- re-implement the proposed method (NEO) and do the comparative evaluations of the main results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: Yes
Justification:
We provide the source code and data to reproduce the main experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ipsscc//pill wwtpcccpppppppppeeeeeeeeeeeeeeee httpa///guddeee/eeeeabiiissssss /Cc////oddiiisssseeeeeee ssiiiiiiccyyyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: Yes
Justification:
We provide all the parameters to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: Yes
Justification: We use 2-sigma error width within the learning plots and state this within the main paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: NA
Justification: We provide the detail on the hardware used to run experiments in supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: paatpa::/neurrpeee htt.://s..cccblllececcccciieeeee
Answer: Yes
Justification:
We have reviewed the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: NA
Justification:
We do not see negativity of societal impacts from our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: NA
Justification:
We do not see how the paper can pose a risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: Yes
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: NA
Justification:
The paper does not release new assets beyond the source code for experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: NA
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: NA
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: NA
Justification: LLMs are not involved in the core method development of this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy httt:p///eerrrree.cc////ofeeeeee for what should or should not be described.
20

---

Appendix
A. Experimental Details
Hardware. All results are obtained using 9900k CPU, 16GB of ram, 256 SSD hard drive and 2080Ti NVIDIA GPU. Results are obtained in hours on local computer.
Parameter settings.
Parameter
Value
Epoch length
2,000 steps
Option initialization probability (inity)
[0.1, 0.2, 0.3, 0.4, 0.5}
Update horizon (H)
5x number of nodes in the domain
Learning rate (a:
0.4
Discount factor (r)
0.99
Epsilon (8)
0.1
Instances per agent
20
Domain size.
Environment
Number of nodes
Number of edges
Four rooms
104
168
Office
2 2558
3 889
Double large maze
5 5363
9010
Tower of Hanoi
729
1 099
Hex
5 5334
8.346
Torus
5 5.336
19028
NYC
10000
25.354
Rubik's cube
151
I 1380
B. Novelty Scaling Function
As noted in the main text, raw novelty counts are scaled by using Equation 2 which has two parameters, 5 and k. Here we present experiments with different values of these parameters in the directed hex domain, shown in Figure 3 where we represent 5 by in the plots. The experimental conditions otherwise identical to those reported in Figure 4 of the main paper.
Dinctee
(Dreced)
(Clcced)
(Denter)
1101
300
4m7
000
400
8-2
(h)
Figure 5: Hyperparameter sweeps of 8 (d) and the directed hex domain.
21

---

C. Solving Eigen-options and Cover-options with Policy Iteration
Hex
Large Maze
Office
Torus (Directed)
Don Tally
Epoch
Cpoch
Cooch
Epoch
[b)
(d)
Figure 6: Comparative sparse reward empirical evaluation of the learning agents with the option discovery methods eigen-option and cover-options with option policies solved using policy iteration across a set of domains.
In the main paper, for all eigenvector- based methods, we derived option policies by using the eigenvector values directly, hill-climbing toward higher values. In the original eigen-options work M. however, option policies are obtained by treating the eigenvector f as potential function and defining an intrinsic reward R(s, a, s') = ((s')]((>)) then solving for the option policy using policy iteration. Here we report results for the eigen-options and cover-options using this original formulation M we construct the intrinsic reward from the associated eigenvector and run policy iteration until the policy stabilizes (using a threshold 0.001 as in the original work (]]. As shown in Figure 0 solving option policies in this manner does not yield a significant performance improvement against the eigen-option and cover-option results for the set of large domains evaluated the main paper.
D. Extension to Continuous Domains
As mentioned in the main paper, if the graph is symmetric, then, for source Laplacian, we can express the Rayleigh quotient [36] as follows:
Pisla - z,)² + EGO
L x.
R(z)
x TJT
x
Σ x
This is the standard Rayleigh quiotient for a symmetric matrix LTT = I- P with the additional term Σx S 2 which is the added squared smoothness error contributions (z(z, 0)2 between the values 2; and the pulls to zero weighted by G. Therefore, extending the proposed method (NEO) to symmetric continuous domains is in principle, simply matter of extending currently Laplacian representation approaches such as 33 by adding a mean square error loss to move sink nodes towards zero based on sink strengths which we can obtain by pseudo-count methods such as distribution random network distillation (5).
E. Bounding Im X())
We proceed in two stages. First, we show that when Ç is sufficiently large, the spectrum of our source Laplacian splits into two distinct families, type 1 eigenvalues (those with [X] 2 () and type 2 eigenvalues (those with X < O), each occupying different region and characterized by different spectral radii. Secondly, we form the Schur complement [37] of a carefully chosen submatrix of the source Laplacian. By working with an expanded version of this complement, we derive bound on the imaginary parts of the type 2 eigenvalues. This is achieved by quantifying how the real and imaginary components of the corresponding eigenvectors interact with the Schur complement. Table 2 gives list of symbols used throughout this section.
22

---

Symbol
Description
Matrix dimension; indices split into S and T
S.T
Index partition with |S| = m. [T] t: S precedes T (block order)
P E Raxx
Row-stochastic: Pij 2 0. Pij =1
Pss. PSt, Prs, PIT
Blocks of after permutation Uniform sink weight applied to $
(> 0
T(()
G.........55.
m Source Laplacian + T(() P
L(C)
A(C)
(5 + I) Pss (the SS block)
B, D.C.D
B -PST, = -Prs. = 1 Prr
spec(X)
Spectrum (set of eigenvalues) of X
Sc(A)
Schur complement (D - X/) - C(A A
(())
Coupling ((A-A) -B)
R(A,C)
(Pss + XC) + 1) in the Neumann series
R2(),9)
Tail Σ R(A, C)
DH. DSH
Symmetric/skew parts: DH 2 (D+ DsH } (D (D-DT)
y
T-block (source nodes block) of an eigenvector of L(C)
x
S-block (sink nodes block) of the same eigenvector Max absolute row-sum operator norm Spectral (Euclidean) operator norm Table 2: List of symbols.
|| 10
12
Standard inequalities and tools
Operator norms and parts: We use I1 to denote the maximum absolute row-sum, |1-1|p the spectral norm. For (possibly complex) matrix M, we write Mf = (M + M²) and Ms# z (M M*).
For real matrix, MM = Mu + Mşn is the split into symmetric and skew-symmetric parts.
E G
Determinant factorization: For block matrix
with E invertible,
H
E F = de(
del
del -E GE-I FF
G
H
where H GF-IFF is known the Schur complement 37
Neumann-series resolvent: If R|]
in an operator norm, then (I R)- Ee= Rd converges
and [I -1 S 1/(1 - [[R)))
Cauchy-Schward Inequality: Given two vectors and v, |uto| < | 1//122
Source Laplacian and block form
Fix n 2 2 and a nonempty T C {1....,,) with [T' 2 t and S = (1.... nn \T with [S] = m.
For define
T(C) diag( S
indices in
indices in T
Here we consider the T-block the source nodes and S-block as sink nodes, with sink strength Ç.
Let P
I p be row-stochastic.
Set L(() = In + r(() - P. After ordering indices so
23

---

S comes first,
L(C) 4()) - ((i)) A(()) C D A())= :-) (c+1)Lm PPss Pss, = 3==-Pr PSTT, C -:= D: 1.-Prr Prr.
B
(3)
Notice that the sink-strength Ç only affects the SS block A()): it appears through the added diagonal damping on the sink-indexed nodes and therefore modifies only the interactions among sinks. The remaining blocks are <-independent: B contains connections from sink nodes to source nodes, C contains connections from source nodes back to sink nodes, and D contains connections among the source nodes themselves.
Schur complement and the T-llock equation
For À C,
M(C) AI, [(()) Alm
B
C
D
Whenever A(C) Xlm is invertible, we can define the Schur complement 37 as:
S₂(A) = (D X4) (A(C)) (1m))11 B.
(4)
Then the block determinant identity gives
det(L(() AIn) = det (A(() Amm) - det Sç(A).
(5)
xx
Moreover, writing an eigenvector of L(C) in blocks as block) of an eigenvector and is the S-block (sink node block) of the eigenvector, the equation is equivalent to
where is the T-block (source node
y
(L(S) AI)
(A(C) Xlm) By=00 0,
Cr (D X1)y 0.
If (() AIn is invertible, then
x = -A(() - AIm) -BBy,
(6)
and substituting into the second block gives
S₂(A) y(A))=0. =0 0.
(7)
Thus we focus on y because is the T-block the full eigenvector and determines x via (6)
Type-Il II region inside |\| < Ç and invertibility of A(C) XI
Lemma 7.1 (Resolvent exclusion). Let A(C) = (c+ Tm Pss with row-stochastic. |f C.
then A(C) Alm is invertible. Hence eigenvalue of A({) lies in {i> < <).
Proof. Factor
A(C) Amm = (S (S +1 11 (4m
Pest- s+1
Let Q = (Pss + ALm)/(S 1). Since P is row-stochastic, ||Pss|oo 1,
[|]1 < |Pss| + |a|
1+
S+1 <
((1) < C)-
C+1
Thus Im Q is invertible by the Neumann series, hence so is A(C) Alm-
Remark 7.1 (Type-ll eigenvalues). Inside the disk ||| < Ç, Lemma 7.1 guarantees A(C) X/m is
invertible. Therefore any eigenvalue of T.(C) with |>| < must satisty det S₂(A) 0. We call such cigenvalues type-Il.

---

Neumann expansion in the smaller disk [X] S rç
Fix Fix0<r< 1 and restrict to |^| S rç. Define
R(A, () Pss + Alm
D0 Ra(A, = R(..))
t+1
For clean, uniform 2-norm bounds on this disk, we assume the gap condition
8: (C + (I) Psslla + r() >
(8)
(Equivalently: [Psss + (.)
Lemma 7.2 (Neumann-series resolvent with tail bound). Assume and ||| I rç. |[(A, l) < 1 and
Then
(A(C) Amm)
c+1 (I R
(9)
and the tail satisfies the uniform bound
( S |R(A 2112 | C)lle
(1Pssll2 + r
(10)
1)+
Proof. First we have:
A(C) - Am = + 1) R(A,)))
(11)
Next since |R(A, < 1,
Psssl2 + [2]
| + +
5
[R(A, -
< 1,
s+1
s+1
++1
so (Im 11-1= = Ei Ri and 9 follows. Finally,
20
8 |R]]
||
R2ll2 =
Σ
R
1
1 |
)=
Using 1 - R| 2 1
PPssliatS C+1
C+1 yields (10)
Theorem 7.3 (Schur expansion). Assume and [X] S rG. Then
CB C(Pss Am)B
C
C(A(C) Amm)-B--
(12)
c+1
(S+
S+1
CB
Sc(A) (D -
<+1 Bc(A),
(13)
where
Ec(A) = C(Pss + ABm) CR22A, B
(14)
(S (5+1)²
s+1
(15)
Proof. Expand C(A(C) - - by inserting 9
C(A(S) Al 1m 1+1
C
(Tm ((
R(A,)) + Re(A.
(16)
CR(A (MAB+CCRAAB+BBB...C...
(17)
(+1
CB
C(Pss + ALmB
CR2(A.C)
(18)
(+1
1I+
c+1
25

---

Then the Schur complement expands as:
(A(A) (D C(A(G) NLm)
(19)
CB
C(Pss Mm)
C
(1-MM) [++
(20)
(1+
c+1
(21)
CB s+1 + E(()
-D
(22)
giving 1B with (A( being collection of the higher order terms of (20).
Lemma 7.4 (Envelope bound on ((A) in |^] S r(). L(t) = C(A(S) Alm) 1 B. Assume
8 and [X] S rÇ. Then
2 IC
[A(a)) S
- + tr)).
6
Proof. From Lemma 7.2
1 5/(C + 5" C+1
[I(A(C) - Amm) 112 ++1 11 -R) -1)-1112 S
5 ++1 1 |||
Therefore
( S |1C|2 - A Amm 1B ||l|||C||
Expanded imaginary-pan bound in | S rc
Theorem 7.5 (Explicit imaginary-part bound (disk [A] < r(). Fix 0 < < and assume 8
Let X()) E spec I.(C) satisfy [X()] S rÇ. Since rς < Ç, Lemma 7.1 implies A(C) A()) m is invertible. Let
x
# be a corresponding eigenvector of L()), written S/T blocks. Then y +
y
satisfies the complemen eigenvector equation
Sc(A(C)) y = 0,
and we assume normalized y that ||y||2 = 1.
Split D = Dy + DSH with DH = [DD + DT) and DSH = - D Because DJH = =DsH (real skew-symmetrii), the scalar y DSHH purely imaginary; hence there exists a({) E E such that
y" DsHY ia()), Define = ||sss|la + rς and 5 as in (8) Then
B(C) = |a(())-
BB| |Cl|2
|| ||C||
a a²
[SA(C) x (()) +
<+1
(C 1)2
0
Proof. From Sx(A)y = and the expansion [3]
0 0= -= AI)) <+1
CB
F<(2) 2=)))=='(() (D)>A)y
AAyy
Ç+ 1/ CBy + 1 Ec())y-
1
(P1)
Write 1 Dy- y" DHV + y" DSHY = DHy + ia({) and take imaginary parts of (PI):
CByyl
(S(() S [a(()
C+1 Ee
(P2)
(i) Since y CBy = (By)* (Cy), Cauchy- Cauchy-Schwarn Schwarz gives
ly CByl ||Byll|[CVlla < ||B||||C|
26

---

iii Using
14 llyl2 = 1, Myl - | and submultiplicatiiity.
[|Psslla + |N
+ (A,
100 Ec( < |B||2||C|2
( 1)2
s+1
With [|] S rC this is
R2(A, 32
EA)ol S |B
(c+
(+1
Finally, apply the tail bound 10
(R2(A.C)
1 a²
a²
s+1
s+1 (5 1)6
(c + 1)28
So
||1|2||C||2
a a²
b;))/))lll 5
r)
(S+ 1)2
Insert (i) and (ii) into (P2) and use B(C) = -a(())
Remark 7.2. D is symmetric, then DAH = 0 so B(C) = 0, and the imaginary part is controlled entirely by the coupling terms that decay with Ç (through factors (C 1)-1 and (C + 1)-2) provided the gap = (C + 1) - Pss + +r) stays positive.
Eigenvalue bound observations
Figure 7 presents nine plots showing the real versus imaginary parts of the eigenvalues of our source Laplacian with a sink strength Ç. According to our theory, the sink strength Ç imposes an upper bound on the imaginary parts of the type-2 eigenvalues. To test this, work the 104-node directed four rooms domain, in which four nodes are designated as sources with sink-strength zero and the remaining 100 nodes as sinks with strength ()_ For each of the nine chosen values of repeat the following 5,000 times: randomly select four source nodes, assign sink-strengths on the remaining 100 nodes, build the directed Laplacian, compute its spectrum, and collect all eigenvalues.
As increases, the two classes of eigenvalues - type I (those farther from zero) and type (those clustering near zero) separate into distinct regions. In particular, the imaginary parts of the type 2 eigenvalues shrink toward zero as grows. When Ç = 0 (in plot a), our Laplacian reduces to the standard random-wald form where there is distinction between type 1 and type 2 cigenvalues, with both having significant imaginary parts. By contrast, at the largest Ç (plot i), only the type eigenvalues that exceed exhibit significant nonzero imaginary parts.
27

---

Figenutture (00)
Dicerustoon L00.3
Eayenvaiian (18.5)
6.75
0.0
6.2
pert
0.5
600
0.2
-.00
-1.00
-130
0.03
0.55
0.5
0T5
1.07
125
1.50
1.5
3.00
0.00
025
0.2
0355
1.00
1355
1.50
1.75
2.00
17
1.0
2.0
(b)
Eiganvelurss of Fanc U1
Egenuslues of and U22
Eignnelluee of
canneke Up
375
035
330
0.2
635
610
8:0
-2.2
-1.00
-1.00
0.5
3.5
255
25
2.
30
35
part
Elgenve of (150)
100
sgoredua dTUG
100
3.75
032
2.50
0.52
800
0.2
-155
.0
-033
-075
-1.1
4genskeec
-482
-1.7
Raal part
(h)
(i)
Figure 7: Eigenvalue plots, where show the real and imaginary parts for source Laplacian under different sink strengths.
28


Reviews:
[{"review_id": "kLgMiTNbJE", "reviewer": "Reviewer_CwLe", "summary": "The paper proposes a technique to improve exploration in reinforcement learning by using global signals from structures like the eigenspectrum of the graph to guide exploration. The key idea is to use the eigenvectors to construct options by following the gradient of the eigenvector to move in the state space. Starting with this intuition the proposed approach takes into account visitation counts to make the options more effective with respect to exploration. Extensive evaluation across multiple domains and other spectral baselines bear out this improvement in exploration performance.", "questions": "- See weaknesses above.", "limitations": "No", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "+ Conceptually the method is quite elegant and simple\n+ Seems to work very well in practice\n+ The paper does a good job of spelling out all the implementation nuances in sufficient detail\n+ The paper has a strong set of theoretical results showing that the proposed approach will take us towards more novel states\n\nWeaknesses\n\n- It would be interesting to explore how the method might generalize to scenarios beyond tabular RL and high dimensional inputs, and scenarios where the state transition graph might not be known in advance and have to be constructed e.g. in a partially observable setting. Would be interesting if the paper discussed some of these practical issues that practitioners often care about in practice.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and your thoughtful comments.\n\n**Questions:**\n\nOur setting does not assume a known graph: the agent adds nodes and edges to the graph through online exploration. During most of the training, the graph is partially observed and often only weakly connected, which motivates a directed formulation of our option method. We discuss the continuous/high-dimensional case in the appendix, noting that our Laplacian formulation is closely aligned with Laplacian representation learning from recent work in high-dimensional Hilbert space [2]. In particular, we discuss how our method differs in construction only by the addition of “sinks” that enforce a zero potential on sink nodes - this addition is straightforward to perform via an MSE penalty for neural network based solutions. We discuss the directed extension in the appendix as well. This extension is omitted from related spectral approaches due to the difficulty of the problem, yet it is crucial in practice: many robotic domains have asymmetric (directed) dynamics. Starting from a directed-theory foundation while staying compatible with Laplacian-style representations makes the approach naturally extensible to high dimensions in the symmetric setting and potentially extendable in the directed setting. In future work, we will work on scaling this to learning directed eigenvectors in high-dimensional directed problems such as robotic domains with strong directed components.\n\n[2] Gomez et al. Proper Laplacian Representation Learning. ICLR, 2024."}, {"review_id": "v772DCvYnc", "reviewer": "Reviewer_xptd", "summary": "This paper presents NEO, an exploration method that leverages the orthogonality of the graph Laplacian's smoothest eigenvectors to extract exploration options. Unlike prior methods which assume an undirected graph, NEO is made compatible with strongly connected directed graphs by limiting eigenvectors to those with a real eigenvalue below a certain novelty threshold. Compared to prior option papers, NEO's options explicitly drive the agent to more novel regions. Experiments on various undirected and directed domains demonstrate that NEO outperforms exploration baselines.", "questions": "Questions\n\n1. \"Count-based exploration methods suffer from lag in exploration and eigenoptions can drive back to frequently visited states\" - does this materialize in experiments?\n2. How is the novelty-based threshold chosen? Does it vary across environments?\n3. Is there a more principled method for choosing the hyperparameters for the raw visitation count scaling function?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The visualizations and toy experiments are compelling case studies that clearly demonstrate that the field of the smoothest eigenvectors corresponds to the more novel regions, illustrating how the method can be used for exploration.\n2. The paper provides solid theoretical support for the proposed method. With small insight on the eigenvalues and modification of the graph Laplacian, the method is extendable to directed graphs, making it more practical.\n\n\n\nNeutral\n\n1. While the writing overall is clear, it is hard to pinpoint what are the specific contributions of the paper. It would be beneficial to highlight them in the introduction. \n\n\n\nWeaknesses\n\n1. There is a lack of analysis for why the baselines perform poorly relative to NEO. For instance, \"Eigen\" gets very low performance despite being intuitively similar to NEO, as it also extracts options from eigenvectors of the graph Laplacian.\n2. The method is not compatible with continuous environments, limiting its usefulness. Furthermore, the requirement of having an approximation of the state transition graph presents a chicken-and-egg problem, where you need good exploration to approximate this graph and you need a good approximation of the graph to perform exploration via NEO. Older works [1] that obtain options from the successor representation for exploration already had some mechanism to bootstrap the approximation of this graph as well as some initial work on extensions to continuous domains.\n\n\n\nFormatting errors impacting readability:\n\n216: Citations for Shortest Path Novelty is broken.\n\n219: Missing dash for Cover options.\n\n221: Epoch is capitalized.\n\n226, 235: figure 2 is not capitalized.\n\n255: figure 3 is not capitalized.\n\n272: \"show\" should be \"shown\".\n\n283: \"cature\" should be \"captured.\" Space between \"atleast\".\n\nFigure 3: the symbols and colors for the methods changes across environments, making it hard to compare.\n\n\n[1] Tomar et al. Successor Options: An Option Discovery Framework for Reinforcement Learning. IJCAI 2019.", "was_revised": true, "final_justification": "I have improved my score to recommend acceptance given the authors' clarifications on their method's improvement over eigenoptions conceptually. The authors have also given sufficient explanation and evidence for NEO's potential to be applied to continuous domains, although they have not shown it directly in the experiments yet. Overall, these initial primary concerns have been alleviated from the rebuttal period.", "rebuttal": "We thank the reviewer for reading our paper and taking the time to write thoughtful strengths and weaknesses.\n# Rebuttal\n\n## Weaknesses\n\n**Weakness 1. There is a lack of analysis for why the baselines perform poorly relative to NEO. For instance, \"Eigen\" gets very low performance despite being intuitively similar to NEO, as it also extracts options from eigenvectors of the graph Laplacian.**\nThank you for the feedback! We include the node count in Figure 4 to evaluate the total number of nodes visited by each method. We will include the visitation matrix plots from which the node counts are obtained in the appendix to further showcase that eigenoptions and covertimes get stuck cycling previously visited states. Although eigenoptions are derived from Laplacian eigenvectors, the resulting behavioural policies do not induce reliable gradients toward distinct states, as is the case for our method. Even the simplest non-trivial eigenvector, the Fiedler eigenvector, is known to fail under certain conditions, such as directionality or multiple graph components, and higher modes are harder to interpret. Moreover, eigenoptions are sign-symmetric: for any option that moves toward a novel region, an opposite-sign option can to undo that progress, driving agents back to frequently visited states. As working graphs increase in node size within our experiments, small local changes will have diminishing impact on global eigenvectors used for eigen options, so the induced policies change little, and this contributes to agents under these policies revisiting the same regions. In our evaluations, eigenoptions and cover-time options underperform a simple, intuitive policy to go to the most novel known state. By contrast, our method’s eigenvectors provide guarantee gradients, avoid sign-symmetric option pairs and produce less stagnant policies in large domains as novelty counts are updated; these differences explain NEO’s performance gap over these baselines.\n\n**Weakness 2. The method is not compatible with continuous environments, limiting its usefulness. Furthermore, the requirement of having an approximation of the state transition graph presents a chicken-and-egg problem, where you need good exploration to approximate this graph, and you need a good approximation of the graph to perform exploration via NEO. Older works \\[1] that obtain options from the successor representation for exploration already had some mechanism to bootstrap the approximation of this graph, as well as some initial work on extensions to continuous domains.**\nWe evaluate in domains where exact eigenvectors are computable, so both baselines (eigenoptions, cover options) and our method are assessed using the eigenvectors they are theoretically intended to have. This does not preclude extensions to continuous domains; however, the distinction between symmetric and directed settings is crucial. As detailed in the appendix, the symmetric case is straightforward: the approach in the paper proper Laplacian representations \\[3] learns eigenvectors in Hilbert-space for \\$L = I - P\\$, while our approach uses \\$L\\_{\\Gamma} = I + \\Gamma - P\\$, where \\$\\Gamma\\$ encodes sink weights that shrink eigenvector values toward zero in proportion to sink strength. Practically, one can add a mean-squared-error (MSE) sink loss (zero at sink states) to pull eigenvector values toward zero with a weight given by the sink strength.\n\nBy contrast, extending to the directed setting is notably more challenging. For instance, \\[2] describe the extension of eigenvector-based distances to directed graphs as a “highly non-trivial challenge” and notes that, “due to the complex-valued eigenvalues of directed graph Laplacian matrices, designing an optimisation objective to approximate the eigenvectors would be difficult.” Beyond our directed gradient guarantees, we make progress by showing in the appendix that our evaluations recover real eigenpairs and by providing an eigenvalue bound induced by the sink weights. In future work, we aim to scale to large **directed** continuous settings by using sinks to bound the imaginary parts of eigenvectors, thereby removing the central obstacle of approximating complex-valued quantities. Whilst this a challenging problem, our work makes important steps in this direction where no other approach to our knowledge provides a potential route to an end-to-end optimisation solution for directed eigenvectors.\n\nWe agree that the “chicken-and-egg” issue is important: effective exploration needs strong representations, yet those representations typically require exploration. Our approach tackles this by coupling exploration with an eigenvector approach, so the learned signals both drive exploration and increasingly reflect the domain’s geometry. Because orthogonality constraints are particularly powerful for representation learning, eigenvector-based methods are natural candidates to address this circularity. However, as our evaluation shows, existing eigenvector option methods underperform on exploration—especially when contrasted with the more intuitive strategy of moving toward novel states.\n\n\n## Questions\n\n**Q1. “Count-based exploration methods suffer from lag in exploration and eigenoptions can drive back to frequently visited states” — does this materialize in experiments?**\n**Yes.** In Figure 4 (node-count evaluations), eigenoptions *start to plateau after initial exploration* in *Double-Maze* and *Double-Hex*, indicating limited discovery of new states. Since exploration of new states starts to plateau in evaluations, it must be concluded that the agent under eigen options moves around frequently visited states more over time. Mechanistically, signed option pairs tend to undo progress toward novelty, and as the graph grows, the Laplacian eigenvectors change little, so the induced behaviours keep revisiting the same regions. This is a crucial issue as it means that eigen options tend to cycle between frequently visited states more as the exploration challenge increases.\n\n**Q2. How is the novelty-based threshold chosen? Does it vary across environments?**\nIn the main paper we use a single global threshold \\$\\delta\\$ across all environments (i.e., no per-task tuning). In the appendix, we ablate this choice by sweeping \\$\\delta\\$. Conceptually, \\$\\delta\\$ is the *base novelty cutoff* in our scaling. As illustrated in Figure 1, with \\$\\delta = 0.5\\$ any eigenvalue \\$\\lambda \\le \\delta\\$ (e.g., \\$\\lambda = 0.4866\\$) satisfies our gradient guarantee. When \\$\\lambda > \\delta\\$, it exceeds the scaled value assigned to the least-novel state, so the sufficient condition used in our proof no longer holds; specifically, the term \\$1/(1 + N(i) - \\lambda)\\$ is not guaranteed to be \\$< 1\\$ for any states \\$i\\$.\n\n**Q3. Is there a more principled method for choosing the hyperparameters for the raw visitation count scaling function?**\nIn the appendix, we show robustness across a range of hyperparameters (Figure 3) and evaluate a simple default: \\$\\delta = 1, k = 1\\$. For a more principled choice, in directed/stochastic domains, the imaginary part of eigenvalues is \\$\\beta\\$-bounded; where it is of interest to avoid imaginary components, a higher \\$\\delta\\$ can be chosen. In undirected (symmetric) domains, a range of values provides similar performance.\n\n[3] Wang et al. Reachability-Aware Laplacian Representation in Reinforcement Learning. arXiv 2022."}, {"review_id": "Vnp8WStd3e", "reviewer": "Reviewer_jL2w", "summary": "The authors introduce Novel Exploration via Orthogonality (NEO), a method to improve exploration in Reinforcement Learning (RL) through option discovery based on spectral graph properties. NEO builds on Laplacian-based approaches by incorporating sink-weights into the graph Laplacian, where sink weights are derived from state visitation counts to encode novelty. The resulting modified Laplacian yields eigenvectors whose gradients guide the agent toward novel regions of the state space. Unlike previous work, NEO extends naturally to both undirected and directed graphs, supported by theoretical guarantees regarding eigenvector properties and gradient flows. The method is evaluated in several RL environments, showing that NEO outperforms existing option discovery baselines, including eigenoptions and cover options.", "questions": "- The experiments are performed exclusively in deterministic settings, while the theoretical formulation of the MDP in the Foundations Section allows for stochastic transitions $\\mathcal{T}(s,a,s’)$. How robust is NEO to non-deterministic environments, where edge weights in the empirical graph reflect averaged, probabilistic transitions rather than deterministic ones?\n- Assumptions in Theorem 3.2: From my understanding, the proof relies on $\\lambda < \\max_i \\gamma_i$, which implies $\\gamma_i > \\lambda$ only under certain conditions, such as a uniform sink set. Additionally, to establish the maximality argument, the existence of at least one source node appears necessary. Could the authors clarify these assumptions explicitly, or correct any misunderstanding?\n- Have the authors considered applying NEO in deep RL environments, where state spaces are continuous and high-dimensional? Even conceptual discussion or preliminary experiments would be valuable to understand potential extensions.\n- The construction of sink weights involves a scaling function $F(.)$ with hyperparameters $\\delta$ and $k$. How sensitive is NEO’s performance to these choices? Can these be linked to the assumptions that eigenvalues $\\lambda$ exists where $N(i) > \\lambda$? \n- Computing eigenvectors for large graphs can be computationally expensive. Can the authors provide runtime comparisons or estimates of computational overhead relative to baselines?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "1. Quality:\n    - Strengths:\n        - The paper presents a technically sound approach, building on solid spectral graph theory foundations.\n        - The paper is generally well structured and well written\n        - The theoretical contributions are well-developed, including $\\lambda$-bounds, gradient guarantees, and proofs of eigenvector properties.\n        - The empirical evaluation is extensive, covering eight domains, both directed and undirected.\n    - Weaknesses:\n        - While the theoretical results are compelling, the practical implications for large, continuous domains are not fully addressed.\n        - Most of the empirical evaluation focuses primarily on discrete, synthetic environments.\n2. Clarity:  \n    - Strengths:\n        - The formalism around the Source Laplacian and the construction of the NEO options is clear and mathematically well-structured.\n        - Algorithm 1 is helpful in understanding the practical implementation of NEO.\n    - Weaknesses:\n        - In Figure 3, inconsistent coloring for baselines makes comparisons, particularly between directed and undirected versions of the same domain, unnecessarily difficult.\n        - Theorem 3.3 suffers from overloaded notation where $i$ is the index of the eigenvector value $f_i$ with $N(i) > \\lambda$ and nodes along a constructed path  $i = v_0 \\rightarrow \\dots \\rightarrow v_k$, which can confuse readers\n        - Minor but noticeable formatting and typographical issues detract from polish, including:\n            - State action pair $(s,a)$ (l.27)\n            - Missing spacing for $\\gamma$ in (l. 95) \n            - max(f(.)) in (l.140)\n            - Buggy reference in (l.216)\n        - References to baseline models in Evaluation setup (l. 210 - 220) are missing which hinders reproducability \n3. Significance: \n    - Strengths:\n        - The empirical results suggest that NEO significantly improves learning efficiency, especially in directed and large-scale domains.\n        - Results seem impactful with NEO outperforming most other approaches in the evaluation\n        - Baselines in the evaluation seem well selected \n    - Weaknesses:\n        - The evaluation is limited to tabular, synthetic domains. Testing on more complex environments (e.g., Atari) would strengthen the practical impact.\n4. Originality: \n    - Strengths:\n        - The introduction of a modified Laplacian with visitation-based sink weights is a novel and meaningful conceptual contribution.\n        - Influences this work is based on are referenced appropriately.", "was_revised": true, "final_justification": "The rebuttal addressed my main concerns regarding robustness in stochastic environments, assumptions in Theorem 3.2, sensitivity to sink-weight scaling, and runtime measurements, providing clear explanations and additional experiments. The rationale for using cosine similarity in high-dimensional experiments was well explained, though I still believe future work could benefit from applying coverage- or reward-based evaluations in more complex, non-tabular domains. Overall, the combination of theoretical contributions, extensive experiments, and satisfactory rebuttal responses outweigh the remaining minor limitations, and I have accordingly increased my score.", "rebuttal": "We thank the reviewer for their careful reading of our paper and their thoughtful questions.\n\n# Q1. Robustness to stochastic transitions\n\n*Reviewer.*  How robust is NEO to non-deterministic environments, where edge weights in the empirical graph reflect averaged, probabilistic transitions rather than deterministic ones?\n\n**Response.**\n\n **NEO** shows similar performance improvements in non-deterministic environments, with the caveat that stochasticity makes exploration harder for any agent (even an optimal policy). To showcase robustness we consider our largest domain, the New York City street graph (10,000 states), with injected “wind” noise of probability 1/4 that the agent moves up regardless of its chosen action. Using the transition matrix augmented with this noise, **NEO** continues to outperform related methods, achieving roughly twice the coverage (unique nodes visited) in a reward-free evaluation. The results are below. We also include Four-Rooms to show a small domain example:\n\n| Domain     | Steps   | Method             | Visited / Total | Coverage % |\n| ---------- | ------- | ------------------ | --------------: | ---------: |\n| NYC        | 250,000 | NEO                |  9,224 / 10,000 |      92.24 |\n| NYC        | 250,000 | SP-Novelty         |  4,566 / 10,000 |      45.66 |\n| NYC        | 250,000 | Q-learning-novelty |  3,217 / 10,000 |      32.17 |\n| NYC        | 250,000 | Eigen-options      |  3,637 / 10,000 |      36.37 |\n| Four-rooms | 10,000  | NEO                |       104 / 104 |     100.00 |\n| Four-rooms | 10,000  | SP-Novelty         |       104 / 104 |     100.00 |\n| Four-rooms | 10,000  | Q-learning-novelty |        53 / 104 |      50.96 |\n| Four-rooms | 10,000  | Eigen-options      |        65 / 104 |      62.50 |\n\n\n*Note: Results are averaged over 20 agent instances; all other settings match the non-stochastic setup used in the paper.*\n\n---\n\n# Q2. Assumptions in Theorem 3.2\n\n*Reviewer.* Assumptions in Theorem 3.2: From my understanding, the proof relies on $\\lambda < \\max_i \\gamma_i$\n, which implies $\\gamma_i > \\lambda$\n only under certain conditions, such as a uniform sink set. Additionally, to establish the maximality argument, the existence of at least one source node appears necessary. Could the authors clarify these assumptions explicitly, or correct any misunderstanding?\n\n**Response.** Thank you for the careful reading. The proof uses the bound \\$|1+\\gamma\\_i-\\lambda|>1\\$ at each sink, so we amend the assumption from \\$\\lambda<\\max\\_i\\gamma\\_i\\$ to the minimal \\$\\lambda<\\min\\_{i:\\gamma\\_i>0}\\gamma\\_i\\$. We also assume there is at least one source node \\$(\\exists i:\\gamma\\_i=0)\\$; this is already implicit in Theorem 3.3 because novelty counts start at \\$0\\$ \\$(\\Gamma\\_{ii}=N(i)\\in\\mathbb{Z}\\_{\\ge 0})\\$, so some node has \\$N(i)=0\\$. With these minimal clarifications, the maximality step follows: no sink attains \\$\\max\\_i |f\\_i|\\$, so any maximizer is a source.\n\n---\n# Q3. Deep RL extension (continuous, high-dimensional)\n\n*Reviewer.* Have the authors considered applying NEO in deep RL environments, where state spaces are continuous and high-dimensional? Even conceptual discussion or preliminary experiments would be valuable to understand potential extensions.\n\n**Response.** Yes. we can show that **NEO** extends to high-dimensional and continuous settings. \nTo extend to the high-dimensional setting, we can amend the smoothness loss from proper Laplacian representation [2] method\nwith an additional smoothness term to zero weight by our sink strengths:\n\n$L_{\\text{approx}}(x) =\\tfrac12\\sum_{ij} P_{ij}(x_i-x_j)^2 +\\sum_i \\big((\\gamma_i x_i - 0\\big)^2,$\n\ni.e., the standard \\$(x\\_i-x\\_j)^2\\$ smoothness plus a shrinkage \\$\\big(\\gamma\\_ix\\_i\\big)^2\\$, with \\$\\gamma\\_i\\$ derived from our sink-weight scaling (e.g., novelty).\nWe discuss this extension in the appendix and how it's based on the Rayleigh quotient for our source Laplacian:\nThat is, If the graph is symmetric, then\n\n$$\nR(x)=\\frac{x^\\top L x}{x^\\top x}\n=\\frac{\\tfrac12 \\sum_{ij} P_{ij}(x_i-x_j)^2 + \\sum_i \\gamma_i x_i^2}{\\sum_i x_i^2},\n$$\n\nwhich is the standard Rayleigh quotient for \\$L=I-P\\$ (with \\$P\\$ symmetric) plus the diagonal term \\$\\sum\\_i \\gamma\\_i x\\_i^2\\$, equivalently the squared smoothness-to-zero contributions at sinks.\nFor the experiments requested, we compare oracle **NEO** eigenpairs to CNN-based approximations on pixel grids, using visitation weights from the analytically computed hitting time from the start state \\$(0,0)\\$ in each experiment. We report cosine similarity for the 11 *smoothest* eigenvectors, averaged over 10 random seeds. These results are solely to demonstrate *extendibility*.\n\n*Why not Atari?* Atari is predominantly *directed* and lacks oracle eigenpairs, so cosine agreement cannot be validated; the pixel grids provide ground truth and are currently the most complex domain where approximated eigenvectors learned end-to-end with neural networks have been compared correctly to oracle eigenvectors.\n\n**Cosine similarity (11 smoothest; mean over 10 seeds).**\n\n| Environment | Mean      | Std       | Median    | Min       | Max       | \\$\\ge 0.99\\$ (count/11) |\n| ----------- | --------- | --------- | --------- | --------- | --------- | ----------------------- |\n| GRIDMAZE-19 | 0.994137  | 0.012108  | 0.9984306 | 0.9563711 | 0.9993445 | 10                      |\n| GRIDMAZE-16 | 0.983047  | 0.025448  | 0.9931449 | 0.9075332 | 0.9966728 | 8                       |\n| GridRoom-4  | 0.988293  | 0.010844  | 0.9916129 | 0.9659867 | 0.9993791 | 6                       |\n| GridRoom-1  | 0.9546429 | 0.0689298 | 0.979806  | 0.7444355 | 0.9983348 | 3                       |\n\n**Per-eigenvector cosine similarities (\\$v\\_1\\$–\\$v\\_{11}\\$); values are means over 10 seeds.**\n\n|                 | \\$v\\_1\\$   | \\$v\\_2\\$   | \\$v\\_3\\$  | \\$v\\_4\\$   | \\$v\\_5\\$   | \\$v\\_6\\$   | \\$v\\_7\\$   | \\$v\\_8\\$   | \\$v\\_9\\$   | \\$v\\_{10}\\$ | \\$v\\_{11}\\$ |\n| --------------- | ---------- | ---------- | --------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ----------- | ----------- |\n| **GRIDMAZE-19** | 0.9563711  | 0.99921966 | 0.9993445 | 0.9985542  | 0.9991034  | 0.9993152  | 0.9984306  | 0.99785894 | 0.99696004 | 0.99832886  | 0.9920205   |\n| **GRIDMAZE-16** | 0.9823314  | 0.9956034  | 0.9962385 | 0.9966582  | 0.9966728  | 0.996615   | 0.99314487 | 0.9917789  | 0.9909922  | 0.96594334  | 0.90753317  |\n| **GridRoom-4**  | 0.9767812  | 0.99859035 | 0.9993791 | 0.99753225 | 0.97569335 | 0.99685365 | 0.9916129  | 0.9977458  | 0.9863626  | 0.98468316  | 0.9659867   |\n| **GridRoom-1**  | 0.96239364 | 0.94523597 | 0.9983348 | 0.96192765 | 0.94789433 | 0.9976875  | 0.98534834 | 0.9970977  | 0.98091066 | 0.979806    | 0.7444355   |\n\nIn the experiments we use all the parameters from the original proper laplacian representation paper for the pixel based CNN tasks, and only add the sink weights to pull eigenvector values closer to zero across the spectrum.\nDirected domains are the critical next step. Classical “directed” Laplacian approaches [4] hinge on the stationary distribution of a directed random walk; in high-dimensional continuous spaces, this is *intractable to obtain without first approximating the geometry to a significant degree, making such methods circular in their intractability. Moreover, any Hermitian method (e.g., stationary-distribution–weighted[4] or magnetic variants[5]) is symmetric by construction and thus cannot fully encode directedness. Truly non-Hermitian formulations preserve direction but introduce complex spectra; handling complex-valued eigenfunctions in learning pipelines (inner products, orthogonality/normalization, and potentially complex-valued networks) is highly nontrivial. Our contribution makes progress: we provide gradient guarantees even if eigenvectors are complex; empirically, our eigenpairs are real and the imaginary part of eigenvalues decreases as \\$\\beta\\$ increases; and we outline source/sink option designs that encourage real spectra. We see these as concrete steps for future work toward a principled method to obtain useful eigenvectors of directed Laplacians in Hilbert space.\n\n---\n\n# Q4. Sensitivity to sink-weight scaling\n\n*Reviewer.* How sensitive is NEO’s performance to these choices? Can these be linked to the assumptions that eigenvalues \n exists where N(i) > $\\lambda$\n?\n\n**Response.**\nIn the appendix (Figure 3) we report a sweep over the hyperparameters δ and k. Across a wide range of values, performance is stable and typically matches the default configuration. Moreover, the method outperforms the competing baselines across hyperparameters, indicating that our approach is not unduly sensitive to δ or k. For a high scaling of k, we form a nearly uniform value for our less novel states and the states at 0 would act as sources - in this sense, we can link certain scaling of k to our first $\\lambda-bound$ $0< R(1) < \\gamma$ in theorem 3.1.\n\n---\n\n# Q5. Runtime and computational overhead\n\n*Reviewer.* Can the authors provide runtime comparisons or estimates of computational overhead relative to baselines?\n\n**Response**\nFor a fair comparison, we use the large maze environment, which has a total of 5363 nodes and 9010 edges and compute the option eigenvectors or path distances on the full graph: \n| Method       | Time (s)  |\n|--------------|----------:|\n| SP-Novelty   | 1.387825  |\n| NEO          | 3.633035  |\n| Eigenoptions | 6.054768  |\n| Covertime    | 41.021344 |\nNote that the eigenvector methods produce 4 options and the SP-novelty produces one.\n\n[3] Wang et al. Reachability-Aware Laplacian Representation in Reinforcement Learning. arXiv 2022.\n\n[4] Chung. Laplacians and the Cheeger Inequality for Directed Graphs. Annals of Combinatorics 2005.\n\n[5] Zhang et al. MagNet: A Neural Network for Directed Graphs. NeurIPS 2021."}]

Author rebuttal:

Meta-review: The paper proposes to use certain Laplacian matrices to guide exploration in discrete tabular reinforcement learning problems, provide the theory that the methods should work in principle and present experiments that the method does indeed work.  The paper is well written.  All reviewers agree that the paper should be accepted (one borderline accept), solid work!
Decision: Accept (poster)