Proper Laplacian Representation Learning
Authors: Diego Gomez
Michael Bowling
Marlos C. Machado
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement learning
Graph Laplacian
Representation learning
Augmented Lagrangian optimization
Hyperparameter robustness
Primary area: reinforcement learning
TL;DR: We propose a theoretically-sound method to learn the Laplacian representation with deep neural networks, addressing limitations of all the previous methods in the literature.

Abstract: The ability to learn good representations of states is essential for solving large reinforcement learning problems, where exploration, generalization, and transfer are particularly challenging. The _Laplacian representation_ is a promising approach to address these problems by inducing informative state encoding and intrinsic rewards for temporally-extended action discovery and reward shaping. To obtain the Laplacian representation one needs to compute the eigensystem of the graph Laplacian, which is often approximated through optimization objectives compatible with deep learning approaches. These approximations, however, depend on hyperparameters that are impossible to tune efficiently, converge to arbitrary rotations of the desired eigenvectors, and are unable to accurately recover the corresponding eigenvalues. In this paper we introduce a theoretically sound objective and corresponding optimization algorithm for approximating the Laplacian representation. Our approach naturally recovers both the true eigenvectors and eigenvalues while eliminating the hyperparameter dependence of previous approximations. We provide theoretical guarantees for our method and we show that those results translate empirically into robust learning across multiple environments.

Published as a conference paper at ICLR 2024
PROPER LAPLACIAN REPRESENTATION LEARNING
Diego Gomez, Michael Bowling", Marloss C. Machado
Department of Computing Science, University of Alberta
Alberta Machine Intelligence Institute (Amii)
Canada CIFAR AI Chair
Edmonton, AB T6G 2R3, Canada
{gomeznor, mbowl ing, machado hea.ddroa.uabbbaa..com
ABSTRACT
The ability to learn good representations of states is essential for solving large re- inforcement learning problems, where exploration, generalization, and transfer are particularly challenging. The laplacion representation is a promising approach address these problems by inducing informative state encoding and intrinsic rewards for cumporally-xxtendee action discovery and reward shaping. To obtain the Laplacian representation one needs to compute the eigensystem of the graph Laplacian, which is often approximated through optimization objectives compat- ible with deep learning approaches. These approximations, however, depend on hyperparameters that are impossible tune efficiently, converge to arbitrary rota- tions of the desired eigenvectors, and are unable to accurately recover the corre- sponding cigenvalues. In this paper introduce theoretically sound objective and corresponding optimization algorithm for approximating the Laplacian repre- sentation. Our approach naturally recovers both the true cigenvectors and eigen- values while eliminating the hyperparameter dependence of previous approxima- tions. We provide theoretical guarantees for method and show that those results translate empirically into robust learning across multiple environments.
INTRODUCTION
Reinforcement learning (RL) is framework for decision-making where an agent continually takes actions in environment and, in doing so, controls its future states. After each action, given the current state and the action itself, the agent receives a reward and next state from the environment. The objective of the agent is to maximize the sum of these rewards. In principle, the agent has to visit all states and try all possible actions reasonable number of times to determine the optimal behavior. However, in complex environments, e.g., when the number of states large or the environment changes with time, this is not plausible strategy. Instead, the agent needs the ability learn representations of the state that facilitate exploration, generalization, and transfer.
The Laplaciann framework (Mahadevan) representation. This representation is based on the graph Laplacian. which, in the tabular case, is matrix that encodes the topology of the state space based on both the policy the agent uses to select actions and the environment dynamics. Specifically, the d-dimensional Laplacian representation is a map from states to vectors whose entries correspond to d eigenvectors of the Laplacian.
2005 Mahadevan & Maggioni 2007) proposes one such
Among other properties, the Laplacian representation induces metric space where the Eu- clidean distance of two representations correlates the temporal distance of their corresponding states; moreover, its entries correspond to directions that maximally preserve state value informa-
tion (Petrik) 2007). Correspondingly, it has been used for reward shaping (Wu al. 2019 Wang state representation for value approximation (c.g.. Mahadevan & Maggioni 2007
ct al. 2023)
Lan et al., 2022 Wang et al. 20222 Farebrother et al., (002),, as a set intrinsic rewards for ex- ploration via lemporally-extendee
actions (see overview by Machado et al. 2023). zero-shot learn- ing (Touati et al. 2023), and to achieve state-of- ofte--oftthed of-the-art performance in sparse reward environments
[Klissarov & Machado, 2023
When the number of states, [S], is small, the graph Laplacian can be represented as a matrix and standard matrix eigendecomposition techniques to obtain its eigensystem and the

---

Published as a conference paper at ICLR 2024
GridRoom-1
GridRoom-16
GridMaze-19
0.01
Average cosine simllrrty
0.02
0.05
0.5
0.4
0.2
2
Gradient steps
Gradlent steps
Gradient steps
Figure 1: Average cosine similarity between the true Laplacian representation and GGDO for dif- ferent values of the barrier penalty coefficient, averaged over 60 seeds, with the best coefficient highlighted. The shaded region corresponds to a 95% confidence interval.
responding Laplacian representation. In practice, however, |S] is large, even uncountable. Thus, at some point it becomes infeasible to directly compute the eigenvectors of the Laplacian. In this context, Wu et al. (2019) proposed scalable optimization procedure to obtain the Laplacian rep- resentation in state spaces with uncountably many states. Such an approach is based on a general definition of the graph Laplacian a linear operator, also introduced by Wu al. (019)) Im- portantly, this definition allows us to model the Laplacian representation as a neural network and to learn by minimizing an unconstrained optimization objective, the graph drawing objective (GDO).
shortcoming of GDO, however, is that arbitrary rotations of the eigenvectors of the Laplacian min- imize the graph drawing objective (Wang et al. (021). This is, in general, undesirable since rotating the eigenvectors affect the properties that make them useful as intrinsic rewards (see Appendix [ more details). As solution, Wang et al. (2021) proposed the generalized graph drawing objective (GGDO), which breaks the symmetry of the optimization problem by introducing a sequence of de- creasing hyperparameters GDO. The true eigenvectors are the only solution this new objective. Despite this, when minimizing this objective with stochastic gradient descent, the rotations of the smallest eigenvector are still equilibrium points the generalized objective. Consequently, there is variability in the eigenvectors one actually finds when minimizing such an objective, depending, for example, on the initialization of the network and on the hyperparameters chosen.
These issues are particularly problematic because it is impossible to tune the hyperparameters of GGDO without already having access to the problem solution: previous results, when sweeping hyperparameters, used the cosine similarity between the true eigenvectors and the approximated solution as a performance metric. To make matters worse, the best hyperparameters are environ- ment dependent, shown in Figure [ Thus, when relying to guarantee an accurate estimate of the eigenvectors of the Laplacian in environments where one does not know these eigenvectors in advance, which obviously defeats the whole purpose. Finally, the existing objectives are unable to approximate the eigenvalues of the Laplacian, and existing heuristics heavily depend the accuracy of the estimated eigenvectors (Wang al. 2023).
GDO, or GGDO, it is impossible
In this work, we introduce theoretically sound max-min objective and a corresponding optimiza- tion procedure for approximating the Laplacian representation that addresses all the aforementioned issues. Our approach naturally recovers both the true eigenvectors and eigenvalues while eliminat- ing the hyperparameter dependence of previous approximations. Our objective, which we call the Augmented I. Lagrangian Laplacian Objective (ALLO), corresponds to a Lagrangian version of GDO augmented with stop-gradient operators. These operators break the symmetry between the rota- tions of the Laplacian eigenvectors, turning the eigenvectors and eigenvalues into the unique stable equilibrium point of min-max ALLO under gradient ascent-desced dynamics, independently of the original hyperparameters of GGDO. Besides theoretical guarantees, empirically demonstrate that our proposed approach is robust across different environments with different topologies and that able to accurately recover the eigenvalues of the graph Laplacian as well.
BACKGROUND
We first review the reinforcement learning setting, before presenting the Laplacian representation and previous work on optimization objectives for its approximating approximation.
We refer the eigenvectors with corresponding smallest eigenvalues the "smallest eigenvectors".
2

---

Published as a conference paper at ICLR 2024
Reinforcement Learning. We consider the setting in which agent interacts with an environ- ment. The environment is reward -agaattt Markov-decision process M = P. with finite state space S {1..... | finite action space A {1. [I,]..,[A[]) transition proba- bility map P S x A + A(S), which maps a state-action pair (s. to a state distribution P(-1s,a) a) in the simplex ((S), and initial state distribution (Ao A(S). The agent is character- ized by the policy tial state So sampled from μo. Then, the agent samples an action Ag from its policy and, as response, the environment transitions to a new state S1. following the distribution P(So, Au). After this, the agent selects new action, the environment transitions again, and so on. The agent- environment interaction determines a Markov process characterized by the transition matrix P., where (P+),.'' = =mEE (8, a) P(6 a) the probability of transitioning from state 8 to state 8 while following policy π.
S + A(4) that it uses to choose actions. At time-step t = 0, an ini-
Laplacian Representation. In graph theory, the object of study is a node set V whose elements are pairwise connected by edges. The edge between pair of nodes o' E V is quantified by a non- negative real number We,x', which is 0 only there is no edge between the nodes. The adjacency matrix, W E TRIV x|VI, stores the information of all edges such that (W),,e' = Wa,er- The degree of node is the sum of the adjacency weights between and all other nodes in V and the degree matrix D RPI is the diagonal matrix containing these degrees. The Laplacian L is defined as L W, and, just as the adjacency matrix, it fully encodes the information of the graph.
If consider the state space of an MDP M the set of nodes, V S, and W determined by Pr. then we might expect the graph Laplacian to encode useful temporal information about M, meaning the number of time steps required to go from one state another. In accordance with Wu et al. 2019). we broadly define the Laplacian in the tabular reinforcement learning setting as any matrix = f(Pr), where f RR x|S] + Sym || (R) )) is some function that maps P. to symmetric matrix For example, if P. is symmetric. the Laplacian is typically defined as either I-P, or L representation matrix (Dayan 1993 Machado et al., 2018). In the case where P_ is not symmetric, is usually defined as L-
(1 A) $ where $ = (I AP, is matrix referred to as the successor
(Pr P to ensure it is symmetric (Wu et al. 2019).
The Laplacian representation, o S Rd. maps state s to d corresponding entries in the set 0 < S [S] smallest eigenvectors of L, i.e. o(s) = [s).s..... "eg].=].,,yys]]] where e, is the i-th smallest eigenvector of L and cs(s). its s-th entry (Mahadevan & Maggioni 2007 Stachenfeld
al. 2014 Machado et al. 2017).
The Graph Drawing Objective. Given the graph Laplacian L, the spectral graph drawing opti- mization problem (Koren 2003) is defined follows:
d
min miy ERS
uu Lu:)
(I)
such that
(u,, = 1
where () )) is the inner product in RIS] and 85z is the Kronecker delta. This optimization problem has two desirable properties. The first one that the d smallest eigenvectors of L are a global optimizer"" Hence, the Laplacian representation & associated with L is solution to this problem. The second property is that both objective and constraints can be expressed as expectations, making the problem amenable to stochastic gradient descent. In particular, the original constrained optimization problem (T) can be approximated by the unconstrained graph drawing objective (GDO):
d ΣΣ (u, u.) 05b)²²
min HER
u. Lu +6
(2)
1=1
1=
Forr ease of exposition, we restrict the notation, theorems, and proofs to the finite state space setting.
However, we generalize all of them to the abstract setting in Appendix A.5 where the state space is an abstract
measure space, in similar fashion as in the work by WW et al. (2019) and Wang et al. (202T).
'The Laplacian has [S] different real eigenvectors and corresponding eigenvalues only it symmetric.
*For proofs in the tabular setting, see the work by Koren (2003) for the case d 2, and Lemma for
arbitrary d. For the abstract setting, see the work hy Wang (02T)
3

---

Published as a conference paper at ICLR 2024
where b oo) is scalar hyperparameter and [uj uu is the vector that results from concatenating the vectors (u,) [Wu et al. 2019
The Generalized Graph Drawing Objective. As mentioned before, any rotation of the smallest eigenvectors of the Laplacian L is global optimizer of the constrained optimization problem (I). Hence, even with an appropriate choice of hyperparameter b. GDO does not necessarily approximate the Laplacian representation Φ. As solution, Wang et al. (2021) present the generalized graph drawing optimization problem:
d
min ucRd 8)
Σ Cs (u, Lu:)
(3)
such that
(u,, us) = dzk. isk
where C1 > >... ca 0 is monotonically decreasing sequence of d hyperparameters. Corre- spondingly, the unconstrained generalized graph drawing objective (GGDO) is defined as:
min WERd18
(u, Lu.) + E min(cy. ((u,, u&) 5,²t²²
(4)
Wang et al. (2021) prove that the optimization problem (3) has a unique global minimum that cor- responds to the smallest eigenvectors of L, for any possible choice of the hyperparameter sequence (c)) However, in the unconstrained setting, which the setting used when training neural net- works, these hyperparameters do affect both the dynamics and the quality of the final solution. In particular, Wang et al. (2021) found in their experiments that the linearly decreasing choice C d - i + performed best across different environments. More importantly, under gradient descent dynamics, the introduced coefficients are unable to break the symmetry and arbitrary rota- tions of the eigenvectors are still equilibrium points (see Corollary ( in Section 4
The Abstract and Approximate Settings. Lastly, the previous optimization problems [-44 can be generalized to the abstract setting, where S is potentially an uncountable measure space (e.g.. the continuous space R"). In practice, the only thing that changes is that finite-dimensional vectors u, are replaced by real-valued functions u, S R and matrices by linear operators that map these functions to functions in the same space (see Appendix A.5 for a detailed discussion). This generalization is useful because allows to introduce function approximators in a principled way. Specifically, we replace the d functions (uI, (4a) by the parametric model do S - IRd, where finite dimensional parameter vector. In our case, de represents a neural network, and 0 a vector containing the weights of the network. This choice allows us to find an approximate solution by iteratively sampling a transition batch, calculating the corresponding optimization objective, and propagating the gradients by means of any stochastic gradient descent-basee optimizer. In the fol- lowing chapters we will see why this gradient descent procedure is incompatible with GGDO and how our proposed objective, ALLO, overcomes this incompatibility in theory and in practice.
AUGMENTED LAGRANGIAN LAPLACIAN OBJECTIVE
In this section introduce a method that retains the benefits of GGDO while avoiding its pitfalls. Specifically, we relax the goal of having a unique global minimum for a constrained optimization problem like (3) Instead, modify the stability properties of the unconstrained dynamics to ensure that the only stable equilibrium point corresponds to the Laplacian representation.
Asymmetric Constraints Generalized Graph Drawing Alternative. We want break the dynamical symmetry of the Laplacian eigenvectors that make any of their rotations an equilibrium point for GDO (2) and GGDO (4) while avoiding the use of hyperparameters. For this, let consider the original graph drawing optimization problem [T] If we set d = 1, meaning we try to approximate only the first eigenvector C1, it is clear that the only possible solution U C1. This happens because the only possible rotations are dej. If we then try to solve the optimization problem for
As consequence, the eigenvectors of the Laplacian are commonly called eigenfunctions. However, tech- nically speaking, the eigenfunctions still eigenvectors the space of square integrable functions.
4

---

Published as a conference paper at ICLR 2024
d = 2, but fix tn C1. the solution will be (uī. uz) (e1, eg), as desired. Repeating this process times, we can obtain o. Thus, we can eliminate the need for the d hyperparameterss introduced by GGDO by solving d separate optimization problems. To replicate this separation while maintaining a single unconstrained optimization objective, we introduce the stop-gradient operator [-] in GDO. This operator does not affect the objective, but it indicates that, when following gradient dynamies, the real gradient of the objective is not used. Instead, when calculating derivatives, whatever is inside the operator is assumed be constant. Specifically, the objective becomes:
d
Σ uu LuA) + b min HER4 OI
E ==1==
Σ (( [ux]) - 6yx)²
(5)
Note that in addition the stop-gradient operators, the upper limit in the inner summation is now the variable j. instead of the constant d. These two modifications ensure that u, changes only to satisfy the constraints associated to the previous vectors (u,)}=² and itself, but not the following ones, i.e., (u))ā= Hence, the asymmetry in the descent direction achieves the same effect as having d separate optimization problems. In particular, as proved in Lemma [2] in the next section, the descent direction of the final objective, yet be defined, becomes 0 only for permutations of subset of the Laplacian eigenvectors, and not for any of its rotations.
Augmented Lagrangian Dynamics for Exact Learning. The regularization term added in all of
the previous objectives (2). (4) and (5) is typically referred to a quadratic penalty with barrier coefficient b. This coefficient shifts the equilibrium point of the original optimization problems (T)
and (3). and one can only guarantee that the desired solution is obtained in the limit b - (see
Chapter 17 by Nocedal & Wright 2006). In practice, one can increase b until a satisfactory solution found. However, not only is there no direct metric tell how close one is to the true solution, but also an extremely large b is empirically bad for neural networks when optimizing GDO or GGDO. As principled alternative, we propose the use of augmented Lagrangian methods. Specifically, we augment the objective (5) by adding the original constraints. multiplied by their corresponding dual variables, (53x) (B5k) SSsSSsd- This turns the optimization problem into the following max-min objective, which we call the augmented Lagrangian Laplacian objective (ALLO):
d (u,
d j
max min B uERdiS)
(u. Lu,)
ΣΣ
Bi (u, [[xl]) 5nk) + ΣΣ (u,,[ux] [ux]] 5yx)² (6)
Sa...... Ba,a] E Rd(d+1)/2 is a vector containing all of the dual variables. There two reasons to introduce the additional linear penalty, which at first glance do not seem to contribute anything that the quadratic one is not adding already. First, for an appropri- ately chosen b, the equilibria of the max-min objective (6) corresponds exactly to permutations of the smallest Laplacian eigenvectors, and only the sorted eigenvectors are a stable solution under gradi- ent ascent-descent dynamics. Second, the optimal dual variables 3 are proportional to the smallest Laplacian eigenvalues, meaning that with this single objective one can recover naturally both eigen- vectors and eigenvalues of L (see the next section for the formalization of these claims). Moreover, the calculation of the linear penalty is a byproduct of the original quadratic one. This means that the computational complexity is practically unaltered, beyond having to update (and store) (dd) dual parameters, which is negligible considering the number of parameters in neural networks.
where B = [$1.1 $2,1, $2,2.
Something to note is that the standard augmented Lagrangian has been discussed the literature as potential approach for learning cigenvectors of linear operators, but dismissed due to lack of em- pirical stability (Pfau et al. 2019). ALLO overcomes this problem through the introduction of the stop-graad -ragddddient operators, which are responsible for breaking the symmetry of eigenvector rotations, in similar way as how gradient masking is used in spectral inference networks (Pfau et al. 2019).
Barrier Dynamics. For the introduced max-min objective to work, in theory, has to be larger than finite value that depends on L. Moreover, if f(Px) in the definition of L is stochastic matrix, which is the case for all definitions mentioned previously, one can exactly determine a lower bound for b, proved in the next section. In practice, however, we found that increasing b is helpful for final performance. In our experiments, we do so in a gradient ascent fashion, just as with the dual variables.
5

---

Published as a conference paper at ICLR 2024
4 THEORETICAL RESULTS
To prove the soundness of the proposed max-min objective, we need show two things: 1) that the equilibria of this objective correspond to the desired eigensystem of the Laplacian, and 2) that this equilibria stable under stochastic gradient ascent-descent dynamics.
As an initial motivation, the following lemma deals with the first point in the stationary setting. While it known that the solution set for the graph drawing optimization problem [ corresponds to the rotations of the smallest eigenvectors of L, the Lemma considers a primal-dual perspective of the problem that allows one to relate the dual variables with the eigenvalues of L (see the Appendix for a proof). This identification is relevant since previous methods are not able recover the eigenvalues.
Lemma Consider a symmetric matrix E [|S| with increasing, and possibly repeated, eigenvalues A1 S ... S (js) and corresponding sequence of eigenvectors (e.) Then, given number of components, S d S (8), the pair (u:) (fj where U. e; and 8ig -xzōjko jks is solution the primal-duat pair of optimizatioo problems corresponding the spectral graph drawing optimization problem (7). Furthermore, any other primal solution corresponds to a rotation of the eigenvectors (c,)
Now that we know that the primal-dual pair of optimization problems associated solution the smallest eigensystem of the Laplacian, the following Lemma shows that the equilibria of the max-min objective (6) coincides only with this solution, up to constant, and any possible permutation of the eigenvectors, but not with its rotations.
has as
Lemma 2. The pair u² 3 is equilibrium pair of the max-min objective (6). under gradient ascent-descent dynamics, if and only if coincides with a subset of eigenvectors of the Laplacian (Bote)) )i for some permutation 8 and 83 -2
Proof. Denoting L the objective (6). have the gradient ascent-deseent dynamical system:
u& ft + 1] = u, [t] Opprimal gu, (u(t), B(t)), A1 S i d.
0C (u(t).
3 t 1] = Byx(t] + Oldual 0ß,k
A1 skkssss
where f E N the time index, Oprimal: Cedual > 0 are step sizes, and gu. is the gradient of L with respect us considering the stop-gradient operator. We avoid the notation V. C to emphasize that Su, is not real gradient, but a direction that ignores what is inside the stop-gradient operator.
The equilibria of our system satisfy ui(l 1] 1 and B5x 1] (.. Hence,
gu. (u', (3) -2L +
Σ j=1
B + 26 (uu) u3) 6 =0, 41 visis
(7)
j=1
ac (u' , 033k
) = (uj. u - 0, vI S sisd
(8)
We proceed now by induction over i, considering that Equation an orthonormal basis. For the base case we have:
S tells us that u" corresponds to
guy (u" f²) 2L + un =0 0.
Thus, conclude that u, is eigenvector (,(1) of the Laplacian, and that 31,1 corresponds to its eigenvalue, specifically 31,1 = 2\ for some permutation o : - S. Now let us suppose that u, Ca(j) and Biz 22, for j < i. Equation (8) for i then becomes:
gu, (u" 22u + Bau + BisCo(s) =0
In general, we can express o as the linear combination u = Σ Ci en() since the eigenvectors
|8|
of the Laplacian form a basis. Also, given that (u,, Up) = 0, we have that cij 0 for < i. Hence,
[s]
i-1
Gig Lea()) + +Ba Σ cge
B
Gi (2\r0)) + Bu)e Σ
Σ
3 e 0.
1=

---

Published as a conference paper at ICLR 2024
By orthogonality of the eigenvectors, we must have that each coefficient is O, implying that B. and either Gú or 3 = -2) The last equation allows us to conclude that a pair (Ca.. Gx) only be different to simultaneously for k such that Xx()) >x(()) ie.. u, lies in the subspace of eigenvectors corresponding to the same eigenvalue, where each point is in itself an eigenvector. Thus, conclude, that u, (s) and Big -22;8.3. desired.
As corollary to Lemma 2 let us suppose that we fix all the dual variables to O, i.c., 83t. 0. Then, we will obtain that the constraints of the original optimization problem (I) must be violated for any possible equilibrium point (see the Appendix for a proof). This explains why optimizing GGDO in Equation (4) may converge to undesirable rotations of the Laplacian eigenvectors, even when the smallest eigenvectors are the unique solution of the original constrained optimization problem.
The point u' is equilibrium point of objectives 2 or 4 under gradient descent dynamics, and only if. for any S i d. there exists a S S such that (u", (u,,u)) # dig. That is, the equilibrium is guaranteed be different to the eigenvectors of the Laplacian.
Corollary 1.
Finally, we prove that even when all permutations of the Laplacian eigenvectors are equilibrium points the proposed objective (6), only the one corresponding to the ordered smallest eigenvectors and its eigenvalues is stable (sce Appendix D for empirical confirmation), in contrast with GGDO.
Theorem 1. The only permutation in Lemma that corresponds to an stable equilibrium point of the max-min objective (6) the identity permutation, under an appropriate selection of the barrier coefficient b, the highest eigenvalue multiplicity is 1. That is, there exist finite barrier coefficient such that i = O₁ and 87 = -2x5 correspond to the only stable equilibrium pair, where x is the i th smallest eigenvalue of the Laplacian and e, its corresponding eigenvector. particular, any b > 2 guarantees stability.
Proof Sketch. Complete proof in the Appendix. We have that gu, and 0C/05, define the chosen ascent-descent direction. Concatenating these vectors and scalars in single vector g(u, 3). the stability of the dynamics can be determined from the Jacobian matrix Jgg). Specifically, all the eigenvalues of this matrix have positive real part in the equilibrium pair u* 3", can conclude that the equilibrium is stable. If there is one eigenvalue with negative real part, then it is unstable (see Chicone 2006 Sastry [0133 Mazumdar et al. 2020). As proved in the Appendix, for any pair isiejs S). there exists a real eigenvalue proportional to Ar()) '4. This means that, unless the a permutation the identity, there will be at least one negative eigenvalue and the equilibrium corresponding to this permutation will be unstable.
EXPERIMENTS
We evaluate three different aspects of the proposed max-mi max-min objective: eigenvector accuracy, eigen- value accuracy, and the necessity of each of the components of the proposed objective
Eigenvector Accuracy. We start by consider- ing the grid environments shown in Figure 2 We generate 200, 000 transition samples in each of them from a uniform random policy and uniform initial state distribution. We use the (r, y) coordinates as imputs to a fully-comnected neural network Φo R²² TRd parameterized by 0, with 3 layers of 256 hidden units to ap- proximate the d di-dinensoonal Laplacian repre- sentation ø, where = 11. The network is trained using stochastic gradient descent with our objective (see Wu al. 2019), for the same initial barrier coefficients in Figure [
+
Grdiccmm-1
GrdMaaa-1
Figure 2: Grid environments. Color is the 2nd
smallest Laplacian eigenvector learned by ALLO.
Figure 3 shows the average cosine similarity of eigenvectors found using ALLO compared to the true Laplacian eigenvectors. In all three environments, learns close approximations of the smallest
'Accompayying code is available here:
3/1 1alpppccccic a an_dual
dynami

---

Published as a conference paper at ICLR 2024
GridRoom-1
GridRoom-16
GridMaze-19
1.0
0.01
Average cosine simllarty
0.02
0.05
0.6
0.5
10
10
20
Gradient steps
Gradient steps
Gradient steps
Figure 3: Average cosine similarity between the true Laplacian and ALLO for different initial values of the barrier coefficient b, averaged over 60 seeds, with the best coefficient highlighted. The shaded region corresponds to a 95% confidence interval.
d- eigeeeevvestos in fewer gradient updates than GGDO (see Figure 1 and without a strong depen- dence on the chosen barrier coefficients.
As second and more conclusive experiment, we select the barrier coefficient with the best perfor- mance for GGDO across the three previous environments (b 2.0), and the best barrier increasing rate, Obarrier: for our method across the same environments (Charrier 0.01). Then, we use these values to learn the Laplacian representation in 12 different grid environments, each with different number of states and topology (see Figure 6 in the Appendix), and consider both the (z, y) and pixel-based representations (each tile of the grid corresponds to pixel), with million samples.
Figure 4 compares the average cosine similarities obtained with each method for the (x. y) rep- resentation (see detailed results for both representations in Appendix [E). In particular, it shows the mean difference of the average cosine similarities across 60 seeds. Noticeably, the baseline fails completely in the two smallest environments (i.e., Gr aMaze-1 and Gri Grize (aMaaze-)) 9), and also fails partially in the two largest ones (i.e., Gri SMridMazee e 32 and Gri dRoom- 64). In contrast, ALLO finds close approximations of the true Laplacian representation across all environments, with the exception of GridRoomSym-44 where still found more accurate representation than GGDO. These results are statistically significant for 9 out of 12 environments, with p-value threshold of 0.01 (see Ta the Appendix). Again, this suggests that the proposed objective is successful in removing the antunable-hyperparameee dependence observed in GGDO.
Eigenvalue Accuracy. The dual variables of ALLO should capture the eigenvalues of their associ- ated eigenvectors. Here, we quantify how well they approximate the true eigenvalues in the same 12 grid environments as in Fi. In particular, we compare our eigenvalue accuracy against those found with a simple alternative method (Wang et al., 2023), based on GGDO and on Monte Carlo approximations. Figure 43 shows that the average relative error for the second to last eigenvalues, meaning all except one, is consistently larger across all environments when using the alternative approach, with significance level of 0.01. This is not surprising given the poor results in eigen- vector accuracy for GGDO. However, in several environments the error is high even for the smallest eigenvalues, despite GGDO approximations being relatively more accurate for the associated eigen- vectors. Across environments and across the eigenspectrum, our proposed objective provides more accurate estimates of the eigenvalues (see Appendix ( for the exact values).
Ablations. ALLO has three components that are different from GGDO: (1) the stop-gradient as a mechanism to break the symmetry, (2) the dual variables that penalize the linear constraints and from which we extract the eigenvalues of the graph Laplacian, and (3) the mechanism mono- tonically increase the barrier coefficient that scales the quadratic penalty. Our theoretical results suggest that the stop-gradient operation and the dual variables are necessary, while increasing the barrier coefficient could be helpful, eventually eliminating the need for the dual variables if all one cared about was to approximate the eigenvectors of the graph Laplacian, not its eigenvalues. section, we perform ablation studies to validate whether these insights translate into practice when using neural networks to minimize our objective. Specifically, in GridMaze-l 9, we compare the average cosine similarity of ALLO, with the same objective but without dual variables, and with GGDO, which does not use dual variables, nor the stop gradient, nor the increasing coefficients. For completeness, also evaluate GGDO objective with increasing coefficients.
this
8

---

Published as a conference paper at ICLR 2024
A
B
G-dRoommym-44
+0.01
0.5
0.0
0,2
GridReem-4-
0.09
GR16 6
GM26 9.25
GridRcom-32
0000
0.00
0.00
Griskoom-16-
|,000
6M9 0.5
GM17 9.25
GridRsam-1-
0.000
GrdMaze
0.25
GridMaze-7-
0.70
04
0.00
GrdMaae 26-
0.07
G932
CRA.
GndMaze 0:01
0.25
GridMaze:17 10000
6464 0.02
GR1
0.1
0.3 0.4 0.s
0.6 0.7
-0.23
Difference of means lavg. cosine similarity)
Index
Figure 4: Difference of cosine similarities when approximating eigenvectors (A), and of relative errors for eigenvalues (B). Error bars show the standard deviation of the differences. GR and GM stand for GridRoom and GridMara black bars correspond to p-values below 0.01.
The curves in each panel of Figure 5 represent the different methods we evaluate, while the different panels evaluate the impact of different rates increase of the harrier coefficient. Our results show that increasing the barrier coefficients is indeed important, and not increasing it (as in GDO and GGDO) actually prevents us from obtaining the true cigenvectors. It is also interesting to observe that the rate in which increase the barrier coefficient matters empirically, but it does not prevent our solution to obtain the true eigenvectors. The importance of the stop gradient is evident when one looks the difference in performance between GGDO and ALLO (and variants), particularly when not increasing the barrier coefficients. Finally, it is interesting to observe that the addition of the dual variables, which is essential estimate the eigenvalues of the graph Laplacian, does not impact the performance of our approach. Based on our theoretical results, we conjecture the dual variables add stability to the learning process larger environments, but we leave this for future work.
Average cosine
1.0
ALLO
(3
Similarity
ALLO (8 =
ALLO 18 =
0.6
GGDO tb m)
GOIDO (6 >)
GGDO 16
GGDO (6 m)
0.2
Claarrier
Gparnter 0.01
Qbarner 0.1
Qbarriir
10
10a
2
10t
10*
Gradient steps
Gradient steps
Gradient steps
Gradient steps
Figure 5: Average cosine similarity for different objectives in the environment GridMaze-19 for initial barrier coefficient = 0.1, and for different barrier increase rates Obbrrier-
CONCLUSION
In this paper we introduced a theoretically sound min-max objective that makes use of stop-gradient operators turn the Laplacian representation into the unique stable equilibrium point of a gradi- ent ascent-descent optimization procedure. We showed empirically that, when applied to neural networks, the objective robust to the same untunable hyperparameters that affect alternative ob- jectives across environments with diverse topologies. In addition, we showed how the objective results in a more accurate estimation of the Laplacian eigenvalues when compared alternatives.
As future work, it would be valuable to better understand the theoretical impact of the barrier coeffi- cient the optimization process. Since we can now obtain the eigenvalues of the graph Laplacian, would be also interesting to see how they could be leveraged, e.g., an emphasis vector for feature representations or as a proxy for the duration of temporally-extendee actions discovered from the Laplacian. Finally, it would be exciting to the impact that having access to proper approxi- mation of the Laplacian will have in algorithms that rely on it (c.g., Wang et al.) 2023 Klissarov & Machado 2023)

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank Alex Lewandowski for helpful discussions about the Laplacian representation, Martin Klissarov for providing an initial version of the baseline (GGDO), and Adrian Orenstein for provid- ing useful references on augmented Lagrangian techniques. The research is supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canada CIFAR AI Chair Program, and the Digital Research Alliance of Canada.
REFERENCES
Carmen Chicone. Ordinary Differential Equations with Applications. Springer, 2006.
Peter Dayan. Improving Generalization for Temporal Difference Learning: The Successor Repre- sentation. Neural Computation, 5(4):613-624, 1993.
Jesse Farebrother, Joshua Greaves, Rishabh Agarwal, Charline Le Lan, Ross Goroshin, Pablo Samuel Castro, and Mare G. Bellemare. Proto-Valus Networks: Scaling Representation Learning with Auxiliary Tasks. In International Conference on Learning Representations (ICLR), 2023.
Yuu Jinnai, Jee Won Park, David Abel, and George Dimitri Konidaris. Discovering Options for Ex- ploration by Minimizing Cover Time. In International Conference on Machine Learning (ICML), 2019.
Martin Klissarov and Marlos C. Machado. Deep Laplacian- based Options for Temporally- Extended Exploration. In International Conference on Machine Learning (ICML), 2023.
Yehuda Koren. On Spectral Graph Drawing. In International Computing and Combinatorics Con- ference (COCOON), 2003.
Charline Le Lan, Stephen Tu, Adam Oberman, Rishabh Agarwal, and Marc Bellemare. the Generalization of Representations in Reinforcement Learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Marlos C. Machado, Mare Bellemare, and Michael Bowling. A Laplacian Framework for Option Discovery in Reinforcement Learning. In International Conference on Machine Learning (ICML), 2017.
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption Discovery through the Deep Successor Representation. In International Conference on Learning Representations (ICLR), 2018.
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.
Sridhar Mahadevan. Proto-value Functions: Developmental Reinforcement Learning. Interna-
tional Conference Machine Learning (ICML), 2005.
Sridhar Mahadevan and Mauro Maggioni. Proto-value Functions: A Laplacian Framework for
Learning Representation and Control in Markov Decision Processes. Journal of Machine Learn- ing Research, 8(10):2169-20) 22331, 2007.
Eric Mazumdar, Lillian J Ratiff, and Shankar Sastry. On Gradient- Based Learning in Continuous Games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Spinger, 2006.
Marck Petrik. An Analysis of Laplacian Methods for Value Function Approximation in MDPs. In International Joint Conference Artificial Intelligence (IJCAI, 2007.
David Pfau, Stig Petersen, Ashish Agarwal, David G. T. Barrett, and Kimberly L. Stachenfeld. Spectral Inference Networks: Unifying Deep and Spectral Learning. In International Conference Learning Representations (ICI.), 2019.
10

---

Published as a conference paper at ICLR 2024
Shankar Sastry. Nonlinear Systems: Analysis, Stability, and Control. Springer, 2013.
Kimberly L. Stachenfeld, Matthew Botvinick, and Samuel J. Gershman. Design Principles of the Hippocampal Cognitive Map. Advances in Neural Information Processing Systems (NeurIPS), 2014.
Ahmed Touati, Jérémy Rapin, and Yann Ollivier. Does Zero-Sho Reinforcement Learning Exist? In International Conference on Learning Representations (ICLR), 2023.
Han Wang, Archit Sakhadeo, Adam M. White, James Bell, Vincent Liu, Xutong Zhao, Puer Liu, Tadashi Kozuno, Alona Fyshe, and Martha White. No More Pesky Hyperparameters: Offline Hyperparameter Tuning for RL. Transactions on Machine Learning Research, 2022, 2022.
Kaixin Wang, Kuangqi Zhou, Qixin Zhang, Jie Shao, Bryan Hooi, and Jiashi Feng. Towards Bet- ter Laplacian Representation in Reinforcement Learning with Generalized Graph Drawing. In International Conference on Machine Learning (ICML), 2021.
Kaixin Wang, Kuangqi Zhou, Jiashi Feng, Bryan Hooi, and Xinchao Wang. Reachability-Awan Laplacian Representation in Reinforcement Learning. In International Conference on Machine Learning (ICML), 2023.
Yifan Wu, George Tucker, and Ofir Nachum. The Laplacian in RL: Learning Representations with Efficient Approximations. In International Conference on Learning Representations (ICLR), 2019.
A ADDITIONAL THEORETICAL DERIVATIONS
A.1 PROOF OF LEMMA D
Proof. Let Byk E R denote the dual variables associated to the constraints of the optimization problem []. and L be the corresponding Lagrangian function:
(Bg))sr))) = uu Lu,) + ΣΣ (a un) 65x).
j=1
Then, any pair of solutions (u, (ijksss must satisfy the Karush-Kunh- Kunh-Tukkk conditions. In particular, the gradient of the Lagrangian should be 0 for both primal and dual variables:
d
Vn, C((u)))) (Bja)as)) = 2L + +33 +
B + Σ 3 =0 visisd;
(9)
j=it1
Ba L((((((())))) (B))) = (uj. u - 6Dス = A1 < k <jsdd.
(10)
The Equation IOP does not introduce new information since it only asks again for the solution set (ut ) to form orthonormal basis. Equation (9) is telling us something more interesting. It asks Luç to be linear combination of the vectors (u: 1 1 i.c., it implies that L always maps uf back to the space spanned by the basis. Since this is true for all i, the span of (uz) must coincide with the span of the eigenvectors (C=(()=)11 for some permutation a S + S, as proved in Proposition I. also in the Appendix. Intuitively, if this was not case, then the scaling effect of X along some Ca(s) would take points that are originally in span u ) outside of this hyperplane.
Since we know that the span of the desired basis is (ean(e )i= for some permutation o S - S, restrict the solution to be set of eigenvectors of L. The function being minimized then becomes Dd -i >a(s) which implies that primal solution is the set of d smallest eigenvectors. Now, any rotation of this minimizer results in the same loss and is also in span(e:)) which implies that any rotation of these eigenvectors is also a primal solution.
Considering the primal solution where u e,, Equation becomes:
d Bieck + Σ 870; =0, V1 S sisd.
Vu, C((e)), (85))ss) = 2(A: + 0e +
jit

---

Published as a conference paper at ICLR 2024
Since the eigenvectors normal to each other, the coefficients all must be O, which implies that the corresponding dual solution is P = -A, and Pjz for j +
A.2 PROPOSITION
Proposition Let T E RSXS be a symmetric matrix, "1 ug IRS and A As E R be its eigenvectors and corresponding eigenvalues. and e1,-.. ea RR be d (d-dimensional orthonor- mal basis of the subspace == se, Then, i is closed under the operation of T, i.e, T(E) _ E, there must exist d didimensional subset of eigenvectors (vi,..., ..a S - Us} such that & coincides with their span, i.e., & = (ppan((v,)) =
Proof. Let w * 0 be vector in E. Then, by definition of &, it can be expressed as a linear combination Σ -i=1 o,e, where a E R, and at least one of the coefficients is non-zero. Let us consider now the operation on w terms of its eigenvectors. Specifically, we can express it as
8
Tw
Xy (u, w)u
which, by linearity of the inner-product, becomes
Tw
a (u, ei) u,
Considering the hypothesis that & is closed under T, we reach a necessary condition:
Σ
ai uuj ei)
uj Σ 3
(11)
where 8 E R, and at least one of them is non-zero.
We proceed by contradiction. Let us suppose that there does not exist a d-dimensional subset of eigenvectors [V1, Va) such that & span((v;))). Since the eigenvectors form basis of the whole space, we can express each e; as linear combinations of the form
Ciuu u, = Σ (uy.c)) u.
c; =
j=1
So, supposing that & does correspond any eigenvector subspace, there must exist d' different indices j1. Ja' and corresponding pairs (in. jk.) such that Civix * O. If this was not the case, this would imply that all the c; lie in the span of some subset of less eigenvectors, and so E would correspond to this span.
Hence, have that the coefficients a, are arbitrary and that at least + 1 inner products are not zero. This implies that w lies in a subspace of dimension at least d++ spanned by the d' eigenvectors Vi..... Va' with V; Ujy- Now, the condition in Equation (TT) requires this subspace to be the same as E, but this is not possible since E is d- dimensooi.nal. Thus, we can conclude that there must Va of such that & span span((v;))) = span((e,).).
exist a basis of dl eigenvectors Vi,
A.3 PROOF OF COROLLARY
Proof. Taking the gradient of GGDO referred to L here, leads us to similar expression in Equation (7) for a pair (u, 3 0) and index i:
C(, = Lu,
Big uj +26
Cig ((u uz) 8,j)u,
12

---

Published as a conference paper at ICLR 2024
where Ctj is some constant function of C, and cj. Comparing with the proof of Lemma in A.1 can notice that there are two key differences: the dual sum Σ Buy u, is now O, and the indices in the barrier term Σ Cyy((u, uz) - dty) go now from to d, as opposed to only to i. require the gradient be well, meaning that is an equilibrium point, then we have that:
Lu Σ Cus uz) 6zy) u,
for some non-zero constants Cij. That is, the vector Lu, has to the subspace spanned by the d vectors u1. different from 0 for some j. But then, this means that the restrictions of the original optimization problem are violated in any possible equilibrium point.
This is only possible, however, if at least of the coefficients (u,, uz) 83
A.4 PROOF OF THEOREM
Proof. Let us define the following vectors defining the descent directions for u and B:
3
0c
8/3,
0c
gu:
032.2
gigg
gu
83
ac
88
gug
883
Then, the global ascent-descent direction can be represented by the vector
gu
ga
To determine the stability of any equilibrium point of the ascent-descent dynamics introduced in Lemma we only need to calculate the Jacobian of g, the matrix J := J(g) whose rows correspond to the gradients each entry of g, and determine its eigenvalues (Chicone 2006).
We proceed to take the gradients of Equation and g
Ju B) uV, (u, (u, TT
(12)
2L + B + 26 (u: u;) 1)I + 2u, @ su] +2 Σ bug ug
if
B. I 2b (u, 11 I n,),
if j:
0,
ifi
0C
Jua,, (u,B)
(u, (u.
-u3 diu u, JJ]=;
(13)
03,1
J (u,
Bu. (u. (3 2u,di,du 1u 8gb);
(14)
033x
JBa J,,0,, (u,8)
(u, 33 0.
(15)
03r
13

---

Published as a conference paper at ICLR 2024
Then, have that in any equilibrium point u", , i... in permutation of the Laplacian eigen- system (as per Lemma the Jacobian satisfies:
i-1
2L 21,1+ Abeo(0) @ ea(() + Σ bea(k) @ (o(k)
i = j;
J,y(u",
(b)n(1) & (r())
if > j
0,
if <
JKH (u", ,g") -e0 010000
Ju
2e 01z00 (o(k))i 6zz);
Jus ("" 0.
Now, we determine the eigenvalues of this Jacobian. For this, we need to solve the system:
Jv = r/v
(16)
where 7) denotes an eigenvalue of the Jacobian and v, its corresponding eigenvector.
To facilitate the solution of this system, we use the following notation:
11,1
1/211
W1
1/22
W
W2
V
Vu =
:
Vd,1
Wd
[a.d]
where w; E RIS), for all 1 s < d, and Pigk E R, for all k $ $ d. With this, the eigenvalue
system (16) becomes:
Σ Jaw Σj= Eier BAa I/W, PSiiiA
(17)
El Jus. Wk 7j/3
PIsssiSA
Since the Laplacian eigenvectors form basis, we have the decomposition w, Σソ= S
Co())))
for some sequence of reals (c,y 1 Hence, replacing the values of the Jacobian components in the upper equation of the system we obtain:
2b( (b(e,()) @ e.()) wy
wy + 2L 2A,1 + 4bea(1) & Co(1) +2
be)(k) @ Co(k) +...
==1
k=1
2e + ( - 891b) pgB 1/W; = 0
[S]
Σ
bej (x6) +2 (A) A.)crea()) + 4be Σ (a()) +...
==1
j=1
14

---

Published as a conference paper at ICLR 2024
[S] = cyCo(1) 0.
+ Co())
Σ (R)
Since the cigenvectors form a basis, we have that each coefficient in the sum of terms we have must be Hence, we obtain the following conditions:
cij cn)2((>0()) X.) 26 na 2bozi Mij. visjkish
(4b - 17) = -2V/
bI
(18)
Cig (3)(((o0S)) 21) - -n)
Each of these conditions specify the possible eigenvalues of the Jacobian matrix J. First and fore- most, the third condition tells us that 7j = 2(Aorr)) - X₂) is an eigenvalue independent of b, for any possible pair S j. Since eigenvalues to be positive, the permutation a S + S must preserve the order for all indexes, which only can be true for the identity permutation. That is, all the Laplacian eigenvector permutations that are not sorted are unstable
supposing the eigenvalues
increasing with their index, for the
In addition, deriving the rest of the eigenvalues from the remaining two conditions in (18) and the second set of equations of the system (17), we obtain a lower bound for 6 that guarantees the stability of the Laplacian representation. particular, from the second set of equations of the system 17 we can obtain a relationship between the coefficients Czy and Cjs with V/j. for all 1 S si d:
18]
J Jo, WR
Σ k=1 -
-
[Ee
CREEO(())
Cij - Cji myy
(19)
k=1
get that 17 2b - 2 These set of eigenvalues (two for each i) always have a positive real part, as long as b strictly positive. In addition, if b 2 1, get purely real eigenvalues, which associated with less oscillatory behavior (see (astryy 2013)).
Replacing this into the second condition in 18
Finally, if we assume that 7) + 2(Aa(1) >ÿ) for j (i.e., ? not an eigenvalue already considered), we must have that Cji = 0, and so, by 19 Cij = mPi-. Replacing this into the first condition in (8). we get that 17 = (Art)) A + b b ~x)
N Thus, if b is larger than the maximal eigenvalue difference for the first d eigenvalues of L, we have guaranteed that these eigenvalues of the Jacobian will be positive. Furthermore, since the eigenvalues restricted to the range [0, 2). have that b > ensures strict stability of the Laplacian representation.
-2 b V((Aat) Xx) 5)2
A.5 ABSTRACT SETTING
For sake of completeness, we now discuss how Lemma and Theorem consider abstract measure state space.
I are affected when we
Abstract measure state spaces. First, our state space is now a triple (S, E, p), where S is a set of states, Σ is an appropriate a alalgebra contained in the power P(S) and whose elements those sets of states that can be measured, and : Σ + 1) is a valid probability measure for the pair (S, Σ). Also, for clarity, let us denote now the state distribution P(s, a) corresponding to the state-action pair (s, as IP(-|s, a). In this manner, while the policy remains the same, the Markov process induced by it cannot represented anymore by matrix P,. In its place, we have now the transition probability map P. S + ((S) defined by (-((sss) = E=EA (Ta)s) a).
Note that this conclusion only apply to the where there repeated eigenvalues. This is the case since otherwise 17 = an eigenvalues and then the Sortman-Grobman theorem that allows to conclude stability is not conclusive.
"The simplex (SS) refers here the of prohability measures defined over (8, E).
15

---

Published as a conference paper at ICLR 2024
Moreover, associated with each transition probability measure (-(())) for S, there is transition probability density, P+((|s)
- [0, oo), defined as the Kadon-Nikodyy derivative pa (s' (s) =
(= This is the same to say that the probability of reaching state in the set C S, starting
dp o'
from state 8, is the integral of the density in B: Pr (B]s) = Js Px pr(dd)))p(ds')).
Abstract Laplacian. Second, let consider the vector space of square p-integrable functions (p) = fu E R [g ( p(ds) < oo}. The measure naturally induces an inner-product in this space, (, (p) x (p) + [0, oo), defined as v2), = Ss vi (8))0(8)) which is the expected correlation of the input vectors v1, 02 E (p) under the measure With this, we can define the transition operator P. (p) (p) as:
[p) / v16 ((d")p(("()))pdds)
Note that, just the original transition matrix P. mapped vectors in IR itself, the transition operator does the same in (p).. Hence, it is its abstract analogous and, correspondingly, we can define the abstract graph Laplacian as the square p-integrable linear operator L = f(Px) in End( End(L²( (p)), where / is the identity linear operator and f (p)) + (nd( is a function that maps Px to self-adjoint square p-integrable linear operator f(P=) That linear operator is self-adjoint means, essentially, that its corresponding density with respect to p is symmetric. Thus, this restriction is equivalent to ask that L a symmetric matrix the finieeddimeniioal case. Hence, when Pr (s((s) * (s(ss''), we can define f in such way that the density of f(P*) is (slss)))) + P=('((s) (see Equation by Wu et al. 2019
Extension of Lemma 2 form as in Equation
After the introduced redefinitions, ALLO takes the exact same functional
max B on (x)
min
Σ (us, Lui) +
Σ>
3yz (lu,, [ullip 8yk) +
(20)
1==1
d
b
(Luy, [ux])p -6,x)²
Ø=1A=1
In the abstract setting, and in general, we can define the differential DF of a linear operator as:
L(u + tv) Lu
DF(u)()] = dt L(u + +t))
lim 1-000
t
Now, let us fix the dual variables B, an index sisa d. and the functions uy with j + i, We denote our ALLOO objective with these fixed values by F; = (3,, (wy) ) (p(p) + (p)). Then, the change of this operator at the function u, direction uy with step size t, where the stop gradient operators affect i now 10 is:
i-1
Fi(u; + -t;))= =
Σ (uy, Lug) + iti
ΣΣ
Byk (lu5, [ual) 6jz) +
1-1
Bike ((u,, [uxl) - 616) + Σ>
[ukl]) -6yz)² +
Am light
km
- -6xx)² + (m4 + to I(u + (v())) +...
Fnd( (p)) denotes the space of endomorphisms of L2()), i.c., the space of linear operators hetween (p) and itself.
This means that [u, tvi] [u.] u4-
16

---

Published as a conference paper at ICLR 2024
Bis (((u + lox), [us + twll), du) b(((us (vs)) Iui reel)> dis)²
3ik ((u, + tv:), (uxl) 6m))
b(((u, + tus). [uxl]> 6xx)²
Bye ((ujs [ + twell) - 6g,) +
Σ
b((ug, Iug + +vulllo -5,)²²
-=
s=++1
(1u))) + t 2( Luihp + Bu(us vilp + 20/us, us) (((ug, [usllip 5ss) +...
Σ (ug, Delp +
Σ krm
blux, U2) (1u [ux])> due) + +O((2).
Hence, we can conclude that its differential, DF,, given by:
Fluu: + +v;) - Fl(u -i) i)
(u:(())
lim t1000
t
=( Loe) + Buruu vilo + 2b/ur, uz) [u.l)o diz) +
Ba (wk: Us)p + Σ bluks uz) ((uss [ux]re 8ok)
2L + Bun + +26((uu) (ue, [u.l)o - 5u) uu + Σ Bueu +...
i-1
+ 2h
((uis [ux]io
8ikk 5sx)us
h=1
U4 2L4 +
Buu + 26 Σ (lut, 8ex) ux
Now, we have that the gradient in an arbitrary inner-product vector space is defined as the vector V (m)) such that [F( = (v, VF(")) That is, the gradient of ALLO with respect to u4, given the stop gradient operators, denoted as g: (3, (u.) is:
9: (w)) = VR((.)) = 2Lu; + Σ Bu
2b
(lus, Ux), - -Ja.) uk
k=1
1=1
We can note that this expression is exactly equivalent to the one obtained in the finite dimensional case in Equation 77. Similarly, one can derive analogous to Equation (8). and, since the proof of Lemma only depends on the properties of the inner product, and not a specific inner product, we can conclude that Lemma 2 applies the general abstract setting as well. In particular, we have that the set of permutations of d eigenvectors of the Laplacian is equal to the equilibria of the gradient ascent-descent dynamics for ALLO
Extension of Theorem I
By analogy with the previous derivation, we can obtain the Hessian of F; with respect to uj, considering the stop gradients (i.e., the gradient of g:), by replacing matrices
Note that our derivation is exactly the same one would follow to calculate the gradient in the finite dimen- sional case if one only uses the definitions of differential and gradient. Under this light, the fact that we are considering abstract spaces instead of finite dimensional ones seems irrelevant for Lemma 2
17

---

Published as a conference paper at ICLR 2024
Then, since the Laplacian is a self- adjoint square p-integrable linear operator, typically called Hilbert-Schmidt integral operator, is also a compact operator. Thus, any vector can be expressed countable sum of eigenvectors, i.e. there are potentially infinite, but at most countable eigenvectors, and so the steps from Equation (77 to Equation (19) still hold, due to the spectral theory of compact operators.
with their linear operator counterparts in Equations 12
15
18

---

Published as a conference paper at ICLR 2024
B ENVIRONMENTS
GridRoom-1
GridMaze-19
GridRoom-64
GridMMaze-9 9
GridMaze-7 7
GridMaze-2e 26
GridMaze-32
GridRoom-4
GridRoomSym-4
GridRoom-32 32
GridMaze-17
Figure 6: Grid environments where the Laplacian representation is learned with both GGDO and ALLO. Color corresponds to the second smallest eigenvector of the Laplacian learned by ALLO.
C LEARNED EIGENVECTORS
Figure Second to seventh Laplacian eigenvectors in increasing order for the environment Gri driidRoom-66 64. The top row corresponds to ALLO, while the bottom one to GGDO. The green bounding boxes indicate the location of local minimum or maximum.
Figure 7 shows the difference between the smallest eigenvectors of the Laplacian (those learned via ALLO) and rotations them (those learned via GGDO). One can note how, in general, the rotations present two characteristics: they have more local minima and local maxima, and their location is distributed irregularly in the state space. The first characteristic relevant considering that the eigenvectors used reward functions discover options, i.e., temporally-extendle actions, that
19

---

Published as a conference paper at ICLR 2024
have sink states these critical states. The more sink states, the shorter the trajectories associated with an induced option, and, as a result, the less exploration.
Similarly, the irregularity is manifestation of cigenvectors of different temporal scales being com- bined, which affects the temporal distance induced by the Laplacian representation. In particular, as studied by Wang et al. (2023), if each eigenvector normalized by their corresponding eigenvalue, the representation distance corresponds exactly to the (square root of the) temporal distance. How- ever, the eigenvalues, which are measure of the temporal scale (see Jinnai al., 2019), are only defined for the original eigenvectors. Hence, the distance induced by the permutations cannot be normalized and, as result, is as suitable for reward shaping.
D LEARNING WITH RANDOM PERMUTATIONS
Average cosine similarity
GrdMaae-117
0.8
GriMazze119
GrddMaze-26
GridMaze-32
0.6
GridMaze-7
Griditom-1
Grditoom-2
GndRcom-64
GridRcomSym.
0.0
0k
75k
100k
175k
Gradient steps
Figure Average cosine similarity between the true Laplacian representation and ALLO for Oharrier 0.01, averaged over 60 seeds. Each 20,000 gradient steps the coordinates of the Laplacian representation are randomly permuted. The shaded region corresponds to a 95% confidence interval.
As an additional sanity check for Theorem 1, FigureBssowss the evolution of the cosine similarity for the 12 grid environments considered under random permutations. Specifically, each 20,000 gradient steps random permutation is sampled and then the output coordinates of the approximator Φe are permuted accordingly. If any arbitrary permutation (or rotation) of the Laplacian eigenvectors were stable, the cosine similarity would decrease after the permutation and it would not increase again. On the contrary, we can observe how in each case learning is as successful as in the initial cycle without permutations.
E AVERAGE COSINE SIMILARITY COMPARISON
In addition to the results considered in Figure Figure 9b shows the cosine similarity for each of the components of the Laplacian representation. It is worth noting that in some environments (c.g., GridRoom-32 32 and aeriddaze-- eetaazee3ee 22) GGDO struggles with the first eigenvectors, which are the most relevant to induce options for exploration.
As supplementary robustness test, we changed the state representation used input the neural network. In particular, we used pixel representation where each tile in the subplots of Figure 6 corresponds to single pixel. this way, the inputs ranged from a size of 9 x 3 to a size of 41 41 x 3. Correspondingly, we added two convolutional layers with no pooling, stride of 2, and kernel size to the previous fully connected network.
Figure 10 contains analogous cosine similarity comparisons to those observed in Figure 9 for the (x. y) state representation. There are three main differences with the previous results. First, the average cosine similarity difference (Figure 10a) is only significant in 7 out of 12 environments, instead of 9 of 12 (see Tables [ and 2). but the difference higher for several environments (c.g., Gri dRoom- 32 and Gr dRoom-11 Second, ALLO only finds the true Laplacian representation
20

---

Published as a conference paper at ICLR 2024
GridRoomSym-4-
H0.01
GridRoom-64
0.23 H
GridRoom-4
0.09
GridRoom-32
0.01
GridRoom-16-
0.00
GridRoom-1
0.00
GridMaze-9
0.62
GridMaze-7-
0.70
GridMaze-32
0.19 H
GridMaze
0.07
GridMaze-19-
0.01
GridMaze-17
0.00
0.0 0.1
0.2
0.3
0.4
0.5
0.6
0.7
Difference of means (avg. cosine similarity)
(a) Average cosine similarity across the d components.
0.05
GRS4
0.00
GM32
0.25
00.5
0.00
GR16
0.005
GM26
0.25
0,000
0.00
1
0.0005
GM9
GM17
0.0000
GM7
GM19
0.025
0.000
1
GR32
0.025
GR4
0.000
0-
0.0025
0.5
0.0000
0.0
2.5
5.0
7.5
10.0
Index
Index
(b) Cosine similarity for each of the components. GR and GM stand for GridRoom and GridMaze. black bars correspond p-values below 0.01.
Figure 9: Cosine similarity difference between ALLO and GGDO when using the (x, y) state representation. Error bars show the standard deviation of the differences. defined as / /o /ALLO o RGGDD. where denotes the sample standard deviation, and n the num- ber of seeds (= 60 in all cases).
in 6 out of 12 environments, as opposed to 1l out of 12. From those 6 where perfect learning is not achieved, 4 have cosine similarity above 0.9, one corresponds to the same environment where the Laplacian representation
not perfectly learned before, and there is one for which the similarity only 0.61. Focusing on these results, we observed that ALLO was able to recover the Laplacian representation for some seeds, but for others the output of the neural network collapsed to constant.
21

---

Published as a conference paper at ICLR 2024
This suggests that maintaining the same hyperparameters with the new state representation and convolutional layers could have resulted in divergence problems unrelated to ALLO. Lastly, we can observe (see Figure T0b) that GGDO fails more frequently, in contrast with the (z, y) representation case, in finding the smallest non-constant eigenvector (e.g.. in Gri wrriRRom-11 6 and Gr dRoom- supporting the hypothesis that GGDO is not scalable to more complex settings, opposed to ALLOO, and preventing the use of the Laplacian for exploration.
GridMaze-11
0.54
GridRoom-4
H 0,10
GridMaze-7-
0.70
GridRoomSym-4-
H 0.00
GridMaze-32
0.04
GridMaze-17
0.03
GridMaze-26-
0.09
GridRoom-32
0.53
GridMaze-19
0.03
GridMaze
0.62
GridRoom-1
0.28
GridRoom-16
0.22
0.0
0.1 0.2 0.3
0.4 0.5 0.6 0.7
Difference of means (avg. cosine similarity)
(a) Average cosine similarity across the d components.
0.25
GR16
GR1
0.00
0.00
1
GM9
GM19 0.055
0.00
GR32
GM26 0.25
0.00
0.05
0.25
0.00
0.00
-0.25
0.05
GRS4
0.000
GM7
1
1
GR4
GM11
Index
Index
(b) Cosine similarity for each of the components. GR and GM stand for GridRoom and Gr i daaze. black bars correspond to p-values below 0.01.
Figure 10: Cosine similarity difference between ALLO and GGDO when using the pixel state representation. Error bars show the standard deviation of the differences, defined as Vo / + o NGGGDO where denotes the sample standard deviation, and n the num- ber of seeds (E [50, 60) in all cases).
/
22

---

Published as a conference paper at ICLR 2024
Env
ALLO
GGDO
t-statistic
p-value
GridMaze- 17
0.9994 (0.0002)
0.9993 (0.0003)
0.641
0.262
GridMaze-19
0.9989 (0.0006)
0.9936 (0.0188)
2.218
0.015
GridMaze-26
0.9984 (0.0007)
0.9331 (0.0517)
9.770
0.000
GridMaze-32
0.9908 (0.0161)
0.8014 (0.0901)
16.018
0,000
GridMaze-7
0.9996 (0.0002)
0.2959 (0.0159)
343.724
0.000
GridMaze-9
0.9989 (0.0007)
0.3755 (0.0081)
596.775
0.000
GridRoom-1
0.9912 (0.0003)
0.9906 (0.0003)
9.691
0.000
GridRoom-16
0.9990 (0.0004)
0.9980 (0.0023)
3.297
0.001
GridRoom-32
0.9982 (0.0010)
0.9857 (0.0266)
3.647
0.000
GridRoom-4
0.9965 (0.0052)
0.9073 (0.0063)
84.136
0.000
GridRoom-64
0.9917 (0.0059)
0.7617 (0.0834)
21.326
0,000
GridRoomSym-4
0.8411 (0.0742)
0.8326 (0.0855)
0.581
0.281
Table 1: Average cosine similarities for ALLO and GGDO when using the (x, y) state repre- sentation. The sample average is calculated using 60 seeds. The standard deviation is shown in parenthesis and the maximal average shown in boldface when the difference is statistically signif- icant, meaning the associated p-value is smaller than 0.01.
Env
ALLO
GGDO
t-statistic
p-value
GridRoom-16 16
0.9992 (0.0003)
0.7836 (0.3897)
4.251
0.000
GridRoom-1
0.9914 (0.0002)
0.7114 (0.4199)
5,080
0.000
GridMaze-9
0.9988 (0.0013)
0.3773 (0.0064)
720.882
0.000
GridMaze-19
0.9789 (0.1354)
0.9480 (0.2032)
0.926
0.178
GridRoom-33
0.9073 (0.2591)
0.3795 (0.4183)
7.917
0.000
GridMaze-26
0.9330 (0.2214)
0.8466 (0.2358)
1.935
0.028
GridMaze-17
0.9995 (0.0001)
0.9687 (0.1658)
1.429
0.079
GridMaze-32
0.6198 (0.3056)
0.5810 (0.3745)
0.598
0.276
GridRoomSym-4
0.8434 (0.0743)
0.8407 (0.0686)
0.197
0.422
GridMaze-7
0.9997 (0.0002)
0.3015 (0.0211)
253.863
0.000
GridRoom-4
0.9965 (0.0076)
0.8950 (0.1065)
7.297
0.000
GridMaze-11
0.9349 (0.0496)
0.3975 (0.0592)
52.931
0.000
Table 2: Average cosine similarities for ALLO and GGDO when using the pixel state representa- tion. The sample average is calculated using 60 seeds. The standard deviation is shown in paren- thesis and the maximal average is shown in boldface when the difference is statistically significant, meaning the associated p-value smaller than 0.01.
23

---

Published as a conference paper at ICLR 2024
F AVERAGE EIGENVALUES
Eny
True
ALLO
GGDO
Eav
True
ALLO
GGDO
GridRoomSym-4
0.0000
0.0000 (0.0000)
0.0000 (0.0000)
GridMaze-32
0,0000
0,0000 (0,0000)
0,0001 (0.00100)
0.0540
0.0429 (0:0003)
0.0395 (0.0003)
0.0000
0,0007 (0.0001)
0.0004 (0.0001)
0,0540
0,0434 (0.0003)
0.0387 (0.0003)
0.0004
0.0008 (0.0000)
0.0006 (0.0000)
0.1068
0,0863 (0.0005)
0,0703 (0.0005)
0.0015 (0.0000)
0.0011 (0.00100)
0,4502
0,4034 (0:0007)
0.0531 (0.0007)
0,0037
0.0035 (0.0000)
0.0033 (0.0000)
0.4507
0.4045 (0,0007)
0.0529 (0.00007
0.0043
0.0040 (0.0000)
0.0038 (0.0000)
0.4507
0.4054 (0.0007)
0.0524 (0.0007)
0.0058
0.0053 (0.0001)
0,0050 (0.0001)
0.4512
0.4066 (0.0008)
0.0520 (0.0008)
0.0063
0.0056 (0.0001)
0.0053 (0.0001)
0.4915
0.4479 (0.0008)
0.01.56 (0.0008)
0.0075
0.0067 (0.0001)
0.0059 (0.0001)
0,4951
0,4513 (0.0007)
0.0121 (0.0007)
0.0099
0.0085 (0.0001)
0.0080 (0.00101)
0.4951
0.4526 (0.0008)
0.0108 (0.0008)
0.0148
0.0126 (0.0001)
0.01 18 (0.0001)
GridRoom-16 16
0,0000
0.0000 (0.0000)
0.0000 (0.0000)
GridMaze-26
0.0000
0.0000 (0.0000)
0.0001 (0.0000)
0,0016
0.0017 (0.0000)
0.0016 (0.0000)
0,0005
0.0008 (0.0000)
0.0007 (0.0000)
0.0063
0.0055 (0.0000)
0.0051 (0.0000)
0.0032 (0.0000)
0.0030 (0.00000)
0,0139
0.01 (0:0001)
0.0111 (0.0001)
0.0039
0.0037 (0.0001)
0,0035 (0.0001)
0.0242
0.0199 (0.0002)
0.0189 (3.0002)
0,0048
0.0044 (0.0001)
0.0039 (0.0001)
0,0367
0.0301 (0:0002)
0.0279 (0.0002)
0.0058
0,0051 (0.0001)
0.0048 (0.0001)
0,0511
0,0420 (0.0002)
0.0382 (0.0002)
0.0094
0.0080 (0.0001)
0.0078 (0.0001)
0,0663
0,0546 (0.00033
0,0452 (0.0003)
0.0129
0.0109 (0.0001)
0.0105 (0.0001)
0,0832
0,0688 (0:0005)
0.0591 (0.0005)
0,0156
0.0131 (0.0001)
0.01 30 (0.0001)
0.1007
0.0836 (0.0006)
0.0691 (0.00166)
0.0195
0.0164 (0.0002)
0.0154 (0.0002)
0.1161
0.0969 (0.0005)
0.0774 (0.0005)
0,0255
0.0213 (0.0002)
0.0201 (0.0002)
GridMaze 9
0,0000
0.0000 (0.0000)
0.0000 (0.0000)
GridMaze 17
0,0000
0,0000 (0.0000)
0.0000 (0.0010)
0.1582
0.1154 (0.0006)
0.0962 (0.0006)
0.0029
0.0027 (0.0000)
0.0026 (0.0000)
0,3083
0,2354 (0.0011)
0.1155 (0.0011)
0.0116
0.0097 (0.0001)
0.0094 (0.0001)
0.4899
0.3961 (0.0015)
0.0181 (0.001.5)
0.0257
0.0212 (0.0001)
0.0199 (0.0001)
0.6613
0.5674 (0.00200)
0,0000 (0.0020)
0,0448
0.0368 (0.0002)
0.0331 (0,0002)
0,7529
0.6692 (0.0024)
0.0000 (0.0024)
0,0682
0.0562 (0.0003)
0.0490 (0.0003)
0.7777
0.6986 (0.0023)
0.0000 (0.0023)
0.0790 (0.0004)
0.0647 (0.00104)
0,8266
0,7585 (0.0027)
0.0000 (0.0027)
0.1251
0.1045 (0.0005)
0.0809 (0.0005)
0,8613
0.8038 (0.0028)
0.0000 (0.0028)
0.1572
0.1327 (0.0005)
0.0950 (0.0015)
0,8768
0.8251 (0:0029)
0.00000 (0.0029)
0.1907
0.1624 (0.0006)
0.1565 (0.0005)
0.8796
0.8292 (0.0029)
0,0000 (0.0029)
0.2249
0.1937 (0.0007)
0,1163 (0.00U7)
GridMaze-7
0,0000
0.0001 (0.0000)
0,0000 (0.0000)
GridMaze-19
0,0000
0.0000 (0.0000)
0.0000 (0. 00000)0))
0,1833
0,1325 (0:0006)
103034400 (0.0006)
0,0016
0,0016 (0,0000)
0.0014 (0,0000)
0,4622
0.3645 (0:0011)
0.0437 (0.001 1)
0.0058
0.0051 (0.0000)
0.0048 (0.0000)
0.5208
0.4186 (0.0010)
0,0000 (0.0010)
0.0066
0.0059 (0.0001)
0.0056 (0.0001)
0,7148
0,6158 (0:0012)
0.0000 (0.0012)
0,0140
0.0117 (0.0001)
0.0111 (0.0001)
0.7958
0.7084 (0,0014)
0.0000 (0.0014)
0.0232
0.0192 (0.0002)
0.0177 (0.0002)
0,8392
0,7621 (0.0014)
0.0000 (0.0014)
0.0365
0,0300 (0.0002)
0.0283 (0.0002)
0.8549
0.7826 (0.0017)
0.0000 (0.001
0.0403
0.0332 (0.0003)
0.0306 (0.0003)
0.8739
0,8076 (0.0015)
0,0000 (0.0015)
0.0516
0.0425 (0.0004)
0.0390 (0.0004)
0.8934
0.8347
(0.0016)
0.0000 (0.0016)
0.0559
0.0461 (0.0003)
0.0416 (0.0000)
0.9091
0.8572 (0.0018)
0.0000 (0.0018)
0.0821
0.0679 (0.0004)
0.0567 (0.0004)
GridRoom-32 32
0.0000
0.0000 (0:0000)
0.0000 (0.0000)
GridRoom-4
0.0000
0.0000 (0.0000)
0.0000 (0.0000)
0,0008
0.0010 (0.0000)
0.0008 (0.0000)
0,0490
0.0392 (0.0003)
0.0357 (0.0003)
0.0018
0.0019 (0.0000)
0.0017 (0.0000)
0.0576
0.0462 (0.0003)
0.0416 (0.0003)
0.0039
0.0036 (0.0000)
0.0051 (0.0000)
0.1
0.0908 (0.0005)
0.0732 (0.0005)
0.0065
0.0057 (0.0001)
0.0053 (0.0001)
0,3905
0,3448 (0.0014)
0.0923 (0.0014)
0.0135
0.01 (0.0001)
0.0105 (0.0001)
0.4420
0.3963 (0.0009)
0.0592 (0.0009)
0.0161
0.0135 (0:0001)
0.0124 (0.0001)
0.4531
0.4080 (0.0010)
0.0517 (0.0010)
0.0200
0.0167 (0.0001)
0.01551 (0.0001)
0.4585
0.4139 (0.0010)
0.0451 (0.0010)
0.0270
0.0223 (0.0002)
0.0206 (0.0002)
0.4787
0.4348 (0.0008)
0.0283 (0.0008)
0.0284
0.0236 (0.0002)
0.0212 (0.0010)
0.4917
0.4489 (0:0010)
0.0152 (0.0010)
0.0364
0,0301 (0.0002)
0.0265 (0.0002)
0.5209
0.4802 (0.0008)
0.0000 (0.0008)
GridRoem-66 64
0.0000
0.0000 (0.0000)
0.0001 (0.0000)
GridRovm- 1
0,0000
0.0000 (0.0000)
0.0000 (0,00100)
0.0004
0.0007 (0.0000)
0.0006 (0.0000)
0.0895
0.0728 (0:0003)
0.0610 (0.0003)
0.0010
0,0012 (0.0000)
0.0009 (0.00100)
0.0895
0.0735 (0.0004)
0.0629 (0.0004)
0.0016
0.0017 (0.0000)
0.0017 (0.0000)
0.1643
0.1372 (0.0005)
0.0986 (0.0005)
0.0020
0.0021 (0:0000)
0.0015 (0.0000)
0.2801
0.2412 (0.0006)
0.1175 (0.0006)
0.0021
0.0022 (0.0000)
0.0018 (0.0000)
0,2801
0,2425 (0.0005)
0.1183 (0.0005)
0.0035
0.0033 (0.0000)
0.0031 (0.0000)
0.3277
0.2868 (0.0007)
0.1128 (0.0007)
0.004]
0.0038 (0.0000)
0.0034 (0.0000)
0.3277
0,2884 (0.0007)
0.1133 (0.0007)
0.0063
0.0055 (0.0000)
0.0051 (0.0000)
0.4376
0,3980
(0.0009)
0.0622 (0.0009)
0.0090
0.0078 (0.0001)
0.0072 (0.0001)
0.4622
0.4229 (0.0008)
0.0432 (0.0008)
0.0097
0.0084 (0:0001)
0.0078 (0.0001)
0.4622
0.4244 (0.0008)
0.0419 (0.0008)
Table 3: Average eigenvalues for ALLO and GGDO. For each environment, the true eigenvalues are shown in decreasing order, from the 2nd one up to the 11... The sample averages are calculated using 60 seeds and in parenthesis are the standard deviations.
24


Reviews:
[{"review_id": "sIWchYxTSQ", "reviewer": "Reviewer_nARE", "summary": "The authors propose a method to approximate the true eigenvalues and eigenvectors of a graph Laplacian relying on an unconstrained max-min problem solved by gradient-based optimization. This can be used to learn good representations for the states in reinforcement learning problems. In the experiments, the efficiency of the method is demonstrated together with an ablation study.", "questions": "Q1. While in the paper the approach focuses on the eigenvectors of the graph Laplacian, in the experiments it is used for finding eigenfunctions. I think that further information should be provided for the actual formulation/solution of this problem.\nQ2. I find Corollary 1 and the paragraph above a bit unclear. Why does an optimum of (2) and (4) imply that the constraint must be violated? \nQ3. Perhaps, an experiment to test the stability of the equilibrium with respect to permutations.\nQ4. Why rotated eigenvectors do not provide a good representation?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This is an interesting and novel approach to the challenging problem of unsupervised representation learning.\n- The technical part of the paper seems to be solid and reasonable, but I have not verified the theoretical results in detail. \n- Both the theoretical results and the experiments support the claims.\n- The paper is relatively well written.", "weaknesses": "I think that the proofs could have been in appendix and instead use the space for more examples, demonstrations, and clarifications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W8EyoqsK0E", "reviewer": "Reviewer_Fii6", "summary": "In Graph Drawing Objective (GDO) and the generalized GDO, the optimization problem in Equation 1 and 3 are used to find the Laplacian representation, but this formulation allows symmetries, which lead to hyper-parameters that can lead to potential issues. The proposed method, Augmented Lagrangian Laplacian Objective (ALLO) in Equation 6, requires no hyper-parameters. In Theorem 1, they show a theoretical result on how there is a guarantee of the stability of the proposed objective function for finding Laplacian representations. The paper concludes with some experiments.", "questions": "- How do you compare the complexity of the proposed objective function optimization problem with previous cases?\n\n\n\n\n\n---------------------------------------------\nAfter the rebuttal: I appreciate the authors for their response. They fully addressed my question and I decided to keep my acceptance score.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- interesting formulation and solution\n- motivated problem\n- having experiments", "weaknesses": "- some parts (e.g., Section 1 and 2) are hard to follow", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vzm54xfypd", "reviewer": "Reviewer_DES2", "summary": "The paper develops three methods for smoothing in state-space models (SSMs). The idea is to assume SSMs that are non-linear and avoid other assumptions like Gaussianity when using variational inference. The drivin gidea is to preserve the temporal structure in the variational proposal. This seems to lead to what is called exponential family dynamical systems, that it a double-looped (forward and backward) chain of markovian conditionals.", "questions": "Not technical questions", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Having carefully checked the exponential family derivations, the parameterization, as well as the derived ELBOs, I feel that likely they are correct and well-founded on previous related work. The use of exponential families in this context, and particularly to build the factorization into markovian conditionals is definitely a strenght. The work itself is clear and concise on the details, also mentioning limitations and reasoning on why certain decisions are taken.", "weaknesses": "To me the paper has two main weaknesses:\n\n[w1] — the paper is in general concise and thorough, but written in a way that the smoothing idea is kind of lost. Particularly, technical details jump in for solving issues of previous technical details (derivations begin at the beginning of pp. 2 and finish at the end of pp. 7). In that way, the paper loses quite a lot of space, and story on the general smoothing idea that authors want to solve (and in which way they want to solve it). \n\n[w2] — the second concern to me is the limited results. Having derived long technical details, the manuscript should at least provide results proportional to the technical development. In my opinion, the evaluation of the model is somehow short (learning of two synthetic systems (pendulum and chaotic scenario) plus analysis on convergence).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OLmaq8CFri", "reviewer": "Reviewer_tVNo", "summary": "This paper proposes a new method for approximating the graph Laplacian (and namely its eigenvectors) over a discrete state space. This paper builds off of the \"graph drawing objective\" (and \"generalized graph drawing objective\"), with the goal to eliminate hyperparameters in its optimization that have been shown to sensitively effect the output approximation of the graph Laplacian's eigenvectors. It achieves this goal with a reformulated minimax objective, and provides both theory and experiments to justify this novel objective.", "questions": "- As there are natural continuous analogs to the graph Laplacion in Euclidean spaces, I am curious how, at least in theory, this framework is extendible into continuous state and action spaces? What are the limitations in extending this theory to continuous settings?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This is a very mathematically clear and concise paper. The objective of the paper is clear and well-presented (re-formulate the graph drawing objective with a smaller hyperparameter space), the solution is clearly presented (convert into a max-min game, in spirit as a replacement to these hyperparameters), and the theory is both mathematically sound and interpretable to understand why the max-min game here achieves the desired objective.\n- While the proposed solution appears \"simple\" on paper, the theory and justification behind the method is both theoretically rich and clever, combining both a nice environment for theoreticians and a direct benefit for practitioners (less hyperparameters to tune alongside the rest of the system).", "weaknesses": "- The primary limitation is my view is the lack of justification in the practical context. Experiments are only provided in very simple maze scenarios, and it is not demonstrated here (or in primary related work I saw) why, in practice, one would chose a Laplacian representation over a standard representation.\n  - On a similar note, there lacks more thorough discussion on the stability of the now-induced minimax game. This likewise seems like something necessary in order to demonstrate practical utility of this framework, at least theoretically.\n\nNonetheless, I feel these weaknesses do not bar this paper from being a good publication as it is. It very clearly and concisely establishes the new method for Laplacian representation learning, and even if this framework is not currently in mainstream practical usage, it gives a solid and approachable platform for future research in improving both theory (e.g. stability of the minimax game could constitute an entirely separate paper) and practice (e.g. implementing standard RL engineering tricks to push practical performance over standard RL methods in certain scenarios).\n\n(However, as a side note, perhaps the current title is a bit presumptuous until such further theory and experimentation has been established.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)