Online Laplacian-Based Representation Learning in Reinforcement Learning
Authors: Maheed H. Ahmed
Jayanth Bhargav
Mahsa Ghasemi
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Representation learning
Online Learning
Graph Laplacian
Primary area: reinforcement_learning
TL;DR: We propose an online method for learning the Laplacian representation in reinforcement learning, and show theoretically and empirically it converges.

Abstract: Representation learning plays a crucial role in reinforcement learning, especially in complex environments with high-dimensional and unstructured states. Effective representations can enhance the efficiency of learning algorithms by improving sample efficiency and generalization across tasks. This paper considers the Laplacian-based framework for representation learning, where the eigenvectors of the Laplacian matrix of the underlying transition graph are leveraged to encode meaningful features from raw sensory observations of the states. Despite the promising algorithmic advances in this framework, it remains an open question whether the Laplacian-based representations can be learned online and with theoretical guarantees along with policy learning. We address this by formulating an online optimization approach using the Asymmetric Graph Drawing Objective (AGDO) and analyzing its convergence via online projected gradient descent under mild assumptions. Our extensive simulation studies empirically validate the convergence guarantees to the true Laplacian representation. Furthermore, we provide insights into the compatibility of different reinforcement learning algorithms with online representation learning.

Online Laplacian-Based Representation Learning in Reinforcement Learning
Maheed H. Ahmed
Jayanth Bhargav!
Mahsa Ghasemi!
Abstract
This makes representation learning important for discov- ering and encoding meaningful features from raw sensory inputs. The main goal of RL is to learn an optimal strat- egy (policy) that maps each state to an action, aiming to maximize the expected reward based on the dynamics of the environment. Learning a good representation can im- prove the sample efficiency of value-function approxima- tion algorithms (Farebrother al., 2023), a major family of RL. algorithms, and enhance generalizations across dif- ferent tasks (Yuan & Lu, 2022). In addition, representation learning has found applications in reward shaping (Wu et al., 2018), learning options with larger coverage (Machado et al., 2017a; Jinnai et al., 2019; Chen et al., 2024), zero-shot learn- ing (Touati et al., 2022), and transfer learning (Gimelfarb et al., 2021: Barreto al., 2017).
Representation learning plays crucial role in re- inforvement learning, especially in complex envi- ronments with high-dimensional and unstructured states. Effective representations can enhance the efficiency of learning algorithms by improving sample efficiency and generalization across tasks. This paper considers the Laplacian-baser frame- work for representation learning, where the eigen- vectors of the Laplacian matrix of the underlying transition graph are leveraged to encode mean- ingful features from raw sensory observations of the states. Despite the promising algorithmic ad- vances in this framework, remains an open ques- tion whether the Laplacian-basee representations can be learned online and with theoretical guaran- tees along with policy learning. We address this by formulating an online optimization approach using the Asymmetric Graph Drawing Objective (AGDO) and analyzing its convergence via online projected gradient descent under mild assump- tions. Our extensive simulation studies empiri- cally validate the convergence guarantees to the true Laplacian representation. Furthermore, we provide insights into the compatibility of differ- ent reinforcement learning algorithms with online representation learning.
A graph representation is often used to learn a representa- tion, i.e., a low-dimensional embedding, of the states (Ma- hadevan & Maggioni, 2007; Wu et al., 2018). States of an environment can be viewed as nodes of a graph, and the tran- sition probability between states under a given policy can be viewed as weighted edges between these nodes. States that are closely connected in the graph are expected have similar representations in the embedding space. One repre- sentation that retains this property is the eigenvectors of the graph Laplacian. Formally, the d-eigenvectors of the graph Laplacian corresponding to the d-smallest eigenvalues are used to construct an embedding function that maps a state to a vector in Rd. We refer to those d-eigenvectors as the d-smallest eigenvectors for the remainder of this paper.
1. Introduction
Constructing the graph and performing eigendecomposi- tion on the Laplacian is only feasible in the tabular settings where the number of states is small. Therefore, Wu et al. (2018) proposed a scalable method to compute the small- est eigenvectors by solving an unconstrained version of the graph drawing objective (Koren, 2005) which is suitable for large and continuous state-spaces. However, the graph drawing objective does not have unique minimizer, rather the rotations of the smallest eigenvectors are also its mini- mizers. To tackle this challenge, Wang et al. (2021) propose the generalized graph drawing objective which breaks the symmetry and only has the smallest eigenvectors as a unique minimizer. Gomez et al. (2023) show that under gradient descent dynamies, the unconstrained version of the general- ized graph drawing objective has permutations of the small-
Representation learning is an important part of machine learning that involves learning compact and useful represen- tations of data. The quality of these representations signifi- cantly impacts the performance and efficiency of machine learning algorithms (Bengio al., 2013). In reinforcement learning (RL), agents often deal with complex environments characterized by high-dimensional and unstructured states.
'Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA. Correspondence to: Mahced H. Ahmed <ahmed237 @ purdu
Proceedings of the 4rnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Laplacian-Basee Representation Learning in Reinforcement Learning
eigenvectors as equilibrium points. They propose the augmented Lagrangian Laplacian objective (ALLO) which has the smallest eigenvectors and the corresponding eigen- values as the stable equilibrium under stochastic gradient descent-ascent dynamics.
contributions below:
We introduce the Asymmetrie Graph Drawing Objec- tive (AGDO), simplified version of ALLO that elimi- nates the need for dual variables.
The Laplacian-basee based representation can computed or learned for a given policy according to its induced Markov chain. However, in RL the policy updates during the training phase as new data comes in, which will in turn necessitate recomputation of the representation. To avoid this complex- ity, in practice, the Laplacian- based representation is learned for a uniformly random policy in a pretraining phase and then used throughout training. Nevertheless, that fixed rep- resentation may not effective for the policies encountered during RL, Recently, Klissarov Machado (2023) showed that learning the representation in online manner while simultaneously updating the policy can improve exploration and increase the total reward. In Figure 1, we illustrate an example, comparing the representations of uniform policy and a non-uniform policy, that further underscores the need for adapting the representation. The non-uniform policy shows that some cells, despite being far from the target in terms of Euclidean distance, actually closer in the embedding space than neighboring cells. This suggests that using the current representation to design rewards could offer a better signal for improving the policy. Klissarov Machado (2023) proposed online deep Laplacian-ber based options for temporally extended exploration where set of policies (also known as options) are trained to select exploratory actions using estimated Laplacian representa- tion of the current overall policy. They provide an extensive empirical analysis of how learning options while updating the representation increase the received rewards; however, the theoretical analysis of online representation learning while updating the policy has remained an open question.
We prove that under gradient descent dynamics, the only stable equilibrium for AGDO is the set of d- smallest eigenvectors.
We theoretically and empirically establish that opti- mizing the online version of AGDO converges to stationary point under the assumption of bounded drift.
2. Literature Review
In this section, review existing studies and research direc- tions in representation learning for reinforeement learning, focusing on topics closely linked to this study.
Proto- Functions. Mahadevan (2005) introduced proto-value functions, set of basis functions that are inde- pendent of the reward function. These functions are defined as the eigenfunctions of the normalized Laplacian of the graph generated by random walk over the state space. This representation has been demonstrated to reduce the number of samples required for training linear value function ap- proximators (Mahadevan Maggioni, 2007). The process of generating the graph involves collecting samples from the environment and connecting neighboring states with edges. However, this method does not adequately account for the stochastic nature of transitions and requires a dis- crete state space. In continuous state settings, Mahadevan (2012) proposes using the Nyström method to interpolate the values of eigenfunctions unseen states based on visited states. Additionally, Xu et al. (2014) suggests enhancing representative state selection by applying K-means cluster- ing to collected samples and constructing graph from the resulting centroids.
Laplacian Representation Using the Graph Drawing Objective. Wu et al. (2018) formulated linear opera- tor that represents the graph over the state-space generated by fixed policy, capturing the stochastic nature of transi- tions, and is applicable to continuous state spaces. They demonstrated that obtaining the eigenfunctions the graph Laplacian. typically solved via the graph drawing objective (Koren, 2005), can be achieved through stochastic optimiza- tion using collected samples without explicitly constructing the graph. Additionally, they illustrated method to re- cover these eigenfunctions up to orthonormal rotation by training neural network. For precise eigenfunction recov- ery, Wang et al. (2021) introduced the generalized graph drawing objective, which breaks the symmetry inherent in
Figure 1: The Laplacian representation of a uniform policy (left) and non-uniform policy (right). The color represents the entry corresponding to each state in the second eigen- vector of the Laplacian. The bordered cell the target.
Motivated by this, we derive a framework for online learn- ing of the Laplacian representation. We summarize our
2

---

Online Laplacian-Basee Representation Learning in Reinforcement Learning
the traditional graph drawing objective. Despite the con- strained generalized objective ensuring the uniqueness of the global minimizer being the Laplacian eigenfunetions, Gomez et al. (2023) demonstrated that stochastic optimiza- tion using the unconstrained objective-employed in neural network training- does not necessarily converge to these eigenfunctions. Consequently, they proposed the augmented Lagrangian Laplacian objective, which has the eigenvectors of the Laplacian the unique stable equilibrium. Other equilibrium points correspond to permutations of the eigen- vectors.
resentations for reinforcement learning algorithm, where they train encoder network using contrastive loss with pairs of images randomly augmented from the same source image. The learned representation is subsequently utilized to train a deep reinforcement learning agent. Furthermore, augmented temporal contrast was developed by Stooke et al. (2021), which involves selecting similar sample pairs from samples that are separated by short time distance. This approach is closely related to the Laplacian approach to representation learning, as states that are connected in the graph have higher probability of appearing in consecutive samples than disconnected states.
Learning the Laplacian representation with any of these objectives is conducted under a fixed policy, typically a uniformly random policy in practice. Klissarov & Machado (2023) introduced online deep covering eigenop- tions (DCEO), online algorithm that concurrentyy learns the Laplacian representation and options (Sutton, 1998), well-established formulation of temporally extended actions in Markov Decision Processes (MDPs). They demonstrated that the online version of DCEO achieves performance com- parable to a two-stage variant of the algorithm, where the representation is learned under fixed uniform policy, with both approaches outperforming other baselines in multiple benchmarks.
In this work, we focus on extending the Laplacian-base representation learning, which has been shown in recent literature to be effective in learning options with high cover- age Machado et al. (2017a); Jinnai et al. (2019); Klissarov & Machado (2023); Chen et al. (2024), to the online set- ting. While empirical results, such as those by Klissarov & Machado (2023), have demonstrated that online repre- sentation learning is effective and promising, a thorough theoretical analysis of the convergence and accuracy of these learned representations in the online setting is still lacking, Therefore, our work seeks address this gap by develop- ing theoretical framework that ensures the stability and accuracy of Laplacian representations in an online learning context.
Successor Features. The deep successor representation, introduced by Kulkarni et al. (2016) as an extension of the successor representation (Dayan, 1993), decomposes the value function into successor feature function and re- ward predictor function. The successor function encodes the discounted expected value of representations of all future states within a given horizon. Leveraging concepts from TD learning and Deep Q-networks (Mnih et al., 2015), both the representation and the successor feature function can be learned simultaneously with neural networks. Successor fea- tures have found diverse applications, such sub-goal states generation in sparse reward environments (Kulkarni et al., 2016), transfer learning (Barreto et al., 2017; Gimelfarb et al., 2021), and options discovery (Machado et al., 2017b; 2023). Notably, Machado et al. (2017b) demonstrated a connection between the eigenvalues and eigenvectors of the successor representation matrix and the eigenvalues and eigenvectors of the normalized Laplacian defined proto- value functions.
3. Preliminaries
In this section, we provide the necessary background to introduce the problem and present the proposed formula- tion and its theoretical analysis. We begin by introducing Markov decision processes within the context of reinforce- ment learning. Next, we highlight the closely related, exist- ing methods of learning the Laplacian representation.
Notation
We use (v,, u) to denote the dot product between two vectors and y. For vector x, the L2 norm, denoted
|x|||, is defined as ||||| v2n
2r 12 The L2 norm of
matrix, is defined as ||||| = sup
Axll and is equivalent to
[
x=0
the spectral norm defined as the largest singular value of the matrix. Finally, the Los norm, denoted || . is the
maximum absolute row sum of the matrix, i.c., || lloc = max, E, laig--
Contrastive Learning in Reinforcement Learning. Con- trastive learning is machine learning method used for learning representations that distinguish between similar and dissimilar pairs of data points using contrastive loss function. Formally, an encoder is tasked with mapping data points to a latent representation where similar points are closely positioned in the latent space. For instance, Laskin et al. (2020) introduced the contrastive unsupervised rep-
Reinforcement Learning. In the reinforcement learning setting, an agent interacts with an environment, which modeled Markov decision process (MDP). A reward agnostic MDP is represented by the tuple (S,A, (oo) Ho) where S is the finite state space, A is the finite actions space, T : S x A + A is the transition probability, and 1l E ASS) is the initial state probability distribution. We consider the environment to be reward-agnostic and
3

---

Online Laplacian-Basee Representation Learning in Reinforcement Learning
that the agent has a policy S + ((A) from which actions are samples each time step. The policy induces Markov chain from the MDP defined by the transition probability p where PT (s,
smallest d-eigenvectors up orthonormal rotation. The graph drawing objective is defined
P(s s'|st
8, TT) = E TT (Taas))(ss(ss a). We assume that the induced Markov chain has a unique stationary distribution p" E ASS). We formally define this in Assumption 4.1.
min WER4
(ui L L"
s.t.
{ugz uk) dzt.
1
Laplacian Representation. A graph is defined by a set of nodes V and an adjacency matrix W E IR [ For two nodes v, v', W Wi is non-zero if and only if there exists an edge from y to v'. The Laplacian matrix L is defined as L = D W where the degree matrix D is diagonal matrix with Du.r= Σح1 W... The Laplacian encodes lot of useful information about the underlying graph. For example, the second to the smallest eigenvalue also known as the Fiedler value determines the algebraic connectivity of the graph (Fiedler, 1973).
where òzk is the Kronecker delta. proximation of GDO is defined as
The unconstrained ap-
d
min WER4
Σ
Lu L uu) +
(uy un) 65x)² 2, (3)
where b is a hyper-parametee
One advantage of using the graph drawing objective is that the unconstrained approximation of the graph draw- ing objective can be optimized by stochastic gradient de- scent using samples collected from the environment with- out constructing the graph or the Laplacian (Wu et al., 2018) ().. Formally, if the inner product is defined in terms of p², the loss can be defined as Σi= (uz, L.us)) H (p1)) P (E (u.(s) (s)))
In the tabular setting, under a fixed policy म, an MDP can be represented as a graph, where V = S and the adjacency matrix V is defined as f(P*) where f maps p" to symmetric matrix. More generally, consider the following formulation given by Wu et al. (2018):
E Egmpt
A Hilbert Space 7t is R [S| with the inner product be- tween two elements u, v E H" defined as (u, u)H= =
The generalized graph drawing objective proposed by Wang et al. (2021) breaks the symmetry in the graph drawing objective and has the set of the smallest d-eigenvectors as a unique minimizer.
Eses u(s))(s))²*(
A linear operator A H== + HT is defined Au(s)
The generalized graph drawing objective (GGDO) defined
Eves AissAAss,a s' (')'uss')ppp))))) (s').
The self adjoint operator W 7² + 7t is defined as
min uERdiS)
cu L Lzus)
(4)
1 (P (*,
1 PT
(8))
+ 2 (s)
(1)
such that
(uys un) = 8jk
1 k.j S d
and the unconstrained approximation of GGDO is defined
The Laplacian L is defined as ===1= V7
as
With slight abuse of notation (RIS), (..))) (..)) + [ (..-)) as a matrix whose en- for
define Apr
tries are defined as Ap- (s, s²) = A(s,s')p" some operator A : H² + HT Note that for a vector u e Isls the matrix multiplication Ap u is equivalent to Au.
min WERd/S
cu L", L"u,)+
(5)
d
min(cy, ok) (luj, uc) 55z)²
j=1
We denote the d-smallest eigenvectors of L ef. eg. ........ .T. The Laplacian embedding function o - Rd embeds a state s to the d-dimensional vector whose i-th element correspond to the s-th element of eT, i.e. o(s) [e] "j.s)....,ee T
The unconstrained GGDO guaranteed to have a unique equilibrium point only in the limit b - oo. However, for other values, rotations of the smallest ddeigenvectors can still be an equilibrium point. The augmented Lagrangian Laplacian objective (ALLO) suggested by (Gomez et al., 2023) is dual objective that has a unique stable equilibrium point of the smallest d-eigenvalues and the corresponding smallest d-eigenvectors. Other unstable equilibrium points
Learning the Laplacian Representation. Optimizing the graph drawing objective (GDO) (Koren, 2005) retrieves the

---

Online Laplacian-Bar Bascd Representation Learning in Reinforcement Learning
correspond to permutations of the eigenvectors and eigen- values. The ALLO is defined as follows
Note that for fixed policy, AGDO is special case of ALLO with / 0. Another similarity between AGDO and ALLO is that AGDO can be viewed as solving ALLO with added regularization for the dual parameters / with a regularization parameter r. Adding a regularization term
max min B weRd
Jui, L. LFus)+
- -r j= Ex=1 fi 2
to (6) yields a closed form solution
Syke (Lug, [uu]] - -8za) +
(6)
for maximization over / with (jx(u) (ug.IuxD ( -6ee Substituting reduces (6) to
((ug. [ux]) - )zx)²
Uug (1) u.) ug0
min MER4
(8)
where [-] is the stop gradient operator, and whatever is inside the operator is treated as a constant when computing the gradient. The stop gradient operator has the same effect breaking the symmetry as the introduction of the constant hyper-parameters in GGDO.
1 (b
(Ru LuxDr - -6a))²
2T
which is the same as ALLO (3 = 0) with b replaced with b + 1 which is also a constant hyperparameter.
2F
We lay the assumptions for our theoretical analysis.
4. Online Learning of the Laplacian Representation
Assumption 4.1. For each policy *t, the induced Markov chain is ergodic and has unique stationary distribution with non-zero entries, i.e., min min pT (s) = Pminn > 0.
We first formulate the problem of learning the Laplacian representation while simultancously updating the policy. We then provide theoretical bounds for the convergence of the learned representation.
#ES
Assumption 4.2. For two consecutive time steps l and ++1, 1, the policies Ti and T&+1 satisfy max
sES EocA| (a
(e)i(a S 8 Additionally, the bound 6 on the policy drift satisfies Σt ((t) =(f(T) for some sub- linear function f.
4.1. Problem Definition
We formulate the problem of learning the Laplacian rep- resentation while the policy is updating as a sequence of Asymmetric GDOs (AGDOs) varying in time. To break the symmetry in GDO we apply the stop gradient operator similar to ALLO. We assume the policy My is initialized randomly and some learning algorithm updates the policy in I' discrete time steps producing a policy ne after each update. Learning the Laplacian representation can then be represented by the sequence of objectives as follows
Assumption 4.1 guarantees that the induced Markov chain has a unique stationary distribution and the induced proba- bility measure p(9) assigns a non-zero value to every state. Assuming unique stationary distribution is common as- sumption in the theoretical reinforcement learning literature (Melo et al., 2008; Even-Dar et al., 2009). Note that go- ing from (s) = O to (s) > 0 is equivalent to adding a node to the graph which would make the dimen- sions of the spaces inconsistent. A more general assump- tion can be made that p(t+1) absolutely continuous with respect p(t), i.. (())(s) = 0 = ((t+ O. in which case, the same analysis can be done to the set S' =s E S - (((+))(s) + 03.
min C. (w) min (EC(F)
(EC( Σ
(uis (t)) 2e)
d
1-1 (luj. [uxl))2(0))+++
(7)
j=1
1=1
Assumption 4.2 assumes the drift in the policy caused by the policy learning algorithm is bounded. This bounded drift assumption valid for many policy learning algorithms in RI. such as trust region policy optimization (TRPO) (Schul- man al., 2015) and proximal policy optimization (PPO) (Schulman et al., 2017). In addition, we require the learning al algorithm to converge to some policy such that the total drift
d
(luz, Us) 25(0 - -
2
where ((1) C Rd is a convex and closed set. We write Le and H. L (() and H()) for simpler notation. In addition, assume that b > 0. We refer to this objective the asymmetric graph drawing objective (AGDO).
The penalty term for the norm of u; does not have the stop gradient operator which does not change the gradient but ensures the term is propagated to the Hessian for the stability analysis. We provide more discussion A.2
'erre have slightly different application of the stop gradi- ent operator than the objective proposed by Gomez al. (2023).
5

---

Online Laplacian-Base Baasd Representation Learning in Reinforcement Learning
is sub-linear in T. For example, two commonly used tech- niques in on-policy deep reinforcement learning-learning rate annealing and gradient clipping (Andrychowicz al., 2020; Engstrom et al., 2020)-a can ensure that the sequence of policy updates remains bounded while gradually decreas- ing over time.
4.3. Convergence Analysis of Online AGDO
In this section, we present a theoretical analysis of the con- vergence of the online PGD algorithm. We first begin by establishing certain properties of the PGD algorithm.
We consider the case where the vectors u are constrained such that their norm is bounded. We define ((+) as (
4.2. Convergence Analysis of AGDO
{u E [Rd[SI; {u,, uz) S } This set has two interesting properties. First, it includes all equilibrium points for all b > 1 (as established in Lemma 4.3). Second, the gradient function g( defined in (9) is Lipchitz continuous over C(1) The following result establishes this property.
We first define the function Pu. Rdiis RIsI, which is the gradient of (7) with respect to u, taking into account the stop gradient operator,
(0)
Proposition 4.5. The loss function f)t) defined in (7) is a-smooth with Lipschitz continuous gradient gl) such that
1-1 (us [uslirco
(l.(4)) = u +2b
Σ j-1
O Opt
1 (u) g'" S al/u u'll
(11)
(2b ((us, 200 - 1) u.) op
(9)
for any u, v' E ClO with a = 2 + 2
12++4d
b.
Pmin
where @ is the Hadamard product. The vectors u, are up- dated using the update equation
Next, we present some preliminary results, which we will later use in the convergence analysis. In Lemma 4.6, we characterize the drift in the policy-induced Markov chain, the Laplacian operator, and the loss function.
u/ (++1) < Projeco (u," (*) - no (z) = u. (0
(10)
Lemma 4.6. Under Assumptions 4. and 4.2, we have the following:
where 17 > 0 is the learning rate, Projece) the projection to (()) and G is the gradient map defined as Glo (n())=
(1) ()) it) - Projecs (u - rigu. (u]
(a) [[pt+])- -p(1)l S 2660)
We show in Lemma 4.3 that for a fixed policy, if c(t) RdS the equilibrium points of performing gradient descent to minimize the function c(t) defined in (7) correspond to permutations of the eigenvectors. We defer all detailed proofs to Appendix A.
(b) [|((t1) - 100 S 60/00 x()
(c) (1((+t1)))))
60 1) 1 1.(t11 -pp(0 21 3 1. (1
ll S 666
p(1)
visT 55 + tb/0) + 5/
Lemma 4.3. If (()) RdSS (+(t) is equilibrium point of the objective (()) in (7) under gradient descent dynamics, iff u.
2d5 Pmin
80a25(0
(d) (c(+))()) c(0 (w) s
(0)
P
a(t) (t)
aa) my and (u,(), u. (40
a(t))
Vue c())
mi
for some permutation a : S -> S where (t) my E 10, i.e. zero or more vectors u. (²()) can be zero.
where 19()) is a condition number on the induced Markov chain by (t).
Note that Lemma 4.6(b) follows directly from previous work on the perturbation analysis of stationary distributions of Markov chains (Haviv & Van der Heyden, 1984; Funderlic & Meyer Jr, 1986; Cho & Meyer, 2000). For example, Cho & Meyer (2000) gives the following condition number maxmax may where mi is the mean first passage x = z J (F) my,!
This result is similar Lemma derived by Gomez et al. (2023) with the norm of the vectors being different and the fact that vectors can be zero. However, we show in Theorem 4.4 that only the identity permutation with non-zero vectors corresponds to a stable equilibrium under proper selection of hyperparameters.
time from state to state and mjj is the mean return time to state j. For other possible options of condition numbers, review the comparative study by Cho & Meyer (2001).
Theorem 4.4. The only stable equilibrium point from Lemma 4.3 minimizing the objective ((9) in (7) under gradi- ent descent dynamics is the one corresponding to the identity permutation with none of the vectors being zero, under an appropriate selection of the barrier coefficient b. if the high- est eigenvalue multiplicity is I.
Finally, we show in Theorem 4.7 that running online pro- jected gradient descent on AGDO achieves ergodic conver- gence.
6

---

Online Laplacian-Basse Based Representation Learning in Reinforcement Learning
Algorithm 1 Online PGD of AGDO
1: Input: Initial policy No, learning rate 7/, initial vector
u( policy learning algorithm A
Coaloe Similariy
2: 1 I" do
3: Interact with the environment and add transitions to the replay buffer
0.8
((+1) + Projecs (u.)) 79h.
(t) (u)
4: "i
5: Get T. by updating Th-1 using A
ALLO
6: end for
0.0
1.5
(a) GridRoom-1
Theorem 4.7. Under Assumptions 4.1 and 4.2, running Algorithm I the sequence of losses as defined in (7) for time steps, with a constant learning rate vj α
1.0
Avaruge Coaine Similarity
0.0
we have,
En- (1,2....TT
[1Gt
0.4
20x
T (1 - - +
(1)) =
((T) T
(12)
AGDO
ALDO
0.2
T
0.0
0.5
1.0
1.5
2.0
Environment Steps
(b) GridMaze-11
where C is the minimum value ((t) can take and G(t) refers to the concatenation of the gradient vectors G Moreover, the OPGD algorithm (Algorithm 1) under the time-varying loss function ((7)) asymptotically converges to the critical point.
Figure 2: Average cosine similarity between the true Lapla- cian representation and the learned representation using AGDO and ALLO for fixed uniform policy.
5. Empirical Analysis
We evaluate the accuracy of the proposed method in the fixed policy setting and the online setting. We evaluate the importance of different components the algorithm as well.
Avarage Coaine Similadty
0.6
Experiments Setup We consider the grid world environ- ments shown in Figure 4. For each experiment, fixed target location is sampled uniformly random, and the agent ceives reward of +1 if the agent reaches the location. For each instance of the environment, fixed target is sampled uniformly at random at the beginning of the training process. At the start of each episode or when the agent reaches the tar- get, the new agent location sampled uniformly at random. We consider maximum episode length of 1000 steps. The matrix P(t) used to compute the Laplacian (00), is defined using weighted sum between the actual p(t) and the ini- tial distribution, as suggested by Wu et al. (2018) 8) to handle episodic Markov Decision Processes (MDPs). To compute the true Laplacian representation, we perform eigen decom- position on the matrix L p(n) which is equivalent to applying the Laplacian operator in the space H(t)
fridRoom-4
GridMaze
GridMare111
1.5 0.0
Environment
(a) AGDO
1.0
Caiine Similarit
0.4
GridRoom
GridRoom-4
GndMare-9
0.2
GridMar-111
0.8
1.0
1.5
2.0
Environment Stupa
x10
(b) ALLO
Figure 3: Average cosine similarity between the true Lapla- cian representation and the learned representation using AGDO and ALLO for ppo policy.
We follow the same setting as Gomez et al. (2023), where we set d = 11 and use the (z. y) coordinates as input to the encoder network, fully connected neural network with

---

Online Laplacian-Bar Based Representation Learning in Reinforcement Learning
(a) GridRoom-1
(b) GridRoom-4
(c) GridMaze-9
(d) GridMaze- 11
Figure 4: Environments tested in experiments where the grey areas are walls.
layers of size 256 each. We start training the encoder and the agent after collecting 10t samples and run the experiment until 2 x 10 samples have been collected. We use fixed value of for the barrier coefficient. The encoder network is trained using an Adam optimizer with learning rate of 10-3 For each collected sample, 10 batches are sampled to update the encoder. For training the agent, we use proximal policy optimization (PPO) (Schulman et al., 2017) as the training algorithm with an initial clipping parameter 0.2 unless otherwise specified. We add an entropy regulariza- tion term to discourage deterministic policies. To simulate assumption 4.2, we schedule the clipping parameter to de- crease from 0.2 to 0.01 starting from step 10s until the end of the training. For the full experimental setup, please refer to Appendix B. We provide an open-source implementa- tion https: /ttgttttttb///gg com/ iine iine_lapll aci ae_aaanreeeeeeeeeeeeeeee http:/hhha...caeaaaaaeeeeeeteete /Mwheeeaaaeeee....e on on. In all figures, report the average cosine similarity of all dimensions of the eigenvectors averaged across 5 seeds with the 95% confidence interval highlighted.
with the number of states, resulting slower convergence. However, this can be mitigated by imposing stricter bounds the drift in the policy learning algorithm.
Ablation Study In this study, we aim analyze three points: (1) the importance of the drift bound assumption, (2) the effect of the number of encoder update steps per sample collected, and (3) the effect of noise caused by sampling from the replay buffer when the policy was different.
To assert the importance of the bounded drift assumption, we compare running PPO with different initial clipping pa- rameters, vanilla policy gradient (VPG) (Sutton al., 1999). and deep Q-network (DQN) (Mnih et al., 2015). First note that VPG is equivalent to PPO without clipping. We can see in Figure 5a that the lower the clipping value is, i.e. the drift bound between policies is smaller, the higher the accuracy for the learned representation is. However, a small drift might affect the performance of the learned policy. In addi- tion, for DQN the change in the policy distribution can be drastic for e-greedy policy with small whenever the Q-network changes the estimated optimal action in state, As for the new estimated optimal action, the probability will shift from [A] to 1 - This explains why the accuracy of the learned representation for DQN is much lower than the on-policy methods. We conclude that the bounded drift assumption is necessary for learning an accurate representa- tion.
Eigenvalue Accuracy (Fixed Setting) We start by com- paring the performance of AGDO to ALLO in the fixed uni- form policy setting. Figure 2, we show that the average cosine similarity of AGDO and ALLO is almost identical for the same initial seeds. This result is similar to the anal- ysis by Gomez et al. (2023) that showed that ALLO with 3 = achieved similar results to ALLO.
In Figure 5b, we analyze the effect of increasing the number of steps. We vary the number of update steps per sample between 1 and 20. While an increase in the number of steps is expected to enhance accuracy, our findings indicate that this is not observed. We hypothesize that this discrepancy due the presence of noise, caused by sampling from the replay buffer.
Eigenvalue Accuracy (Online Setting) Figure 3 shows the results of optimizing both AGDO and ALLO in an online setting where the agent's policy is updated with the PPO loss. Similar to the fixed setting, the results of AGDO and ALLO are almost identical for the same set of seeds. In addition, for all environments, the average similarity trends upward as the training steps increase. For environments with a large number of states (GridRoom-I and GridRoom-4) we notice that the accuracy is slightly lower at earlier stages of the training, which is coherent with our theoretical analysis (see Lemma 4.6 and Theorem 4.7) that the drift increases
To confirm the previous hypothesis, we test in Figure 5c the effect of varying the replay buffer size. Recall that es- timating the AGDO loss (7) is done through sampling steps from the replay buffer. In the online setting, the buffer would include steps from previous policies with different
8

---

Online Laplacian-Baen Baased Representation Learning in Reinforcement Learning
1.0
1.0
1.0
Averrpp Costoe Simkartty
0.0
Average Simzartiy
-0.8
Aversp Coston Simiart
0.0
10.6
-0.6
0.6
-0.4
-0.4
0.4
FPO 0.01 0.01
Steps-1
Episodes #1
Steps=5
Episodes=20
DQN
0.2
Steps=10 10
-0.2
Episodes-
-0.2
Staps=20
Episodes
0.0
0.0
0.0
2.0
Environment Steps
Envireament Steps
Environment Stops
(a) Effect of drift
(b) Effect of number of update steps
(c) Effect of replay buffer size
Figure 5: Analysis of different aspects of online AGDO. (a) The effect bounded drift on the accuracy of the learned representation. (b) The effect of the number of update steps per sample collected. (c) The effect of the number of episodes in the replay buffer.
stationary and transition distributions which would intro- duce bias to our loss estimate. However, small buffer size would also increase the variance of the estimate. This is confirmed by the results, as for a buffer that holds only one episode we see a worse performance than a buffer that holds 20 episodes. On the other hand, increasing the buffer size drastically also causes accuracy drop the samples used have different distribution which can be seen for buffers with sizes 50 and 400.
Acknowledgements
This work was supported in part by the National Aeronautics and Space Administration under Grant 80NSSC24M0070.
Impact Statement
This work focuses on efficient online representation learning in reinforcement learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
6. Conclusion and Future Work
In this paper, we studied online Laplacian- spased representa- tion learning and demonstrated that can be effectively inte- grated with reinforcement learning, enabling simultaneous updates of both representation and policy. Our theoretical analysis, under mild assumptions, shows that rumning the online projected gradient descent on the Asymmetric Graph Drawing Objective achieves ergodic convergence, ensuring that the learned representations are aligned with the underly- ing dynamics. Additionally, our empirical studies reinforce these findings and give insight into the compatibility of re- inforcement learning algorithms with online representation learning.
References
Andrychowicz, M., Raichuk, A., Stanczyk, P., Orsini, M., Girgin, S., Marinier, R., Hussenot, L., Geist, M., Pietquin, O., Michalski, M., et al. What matters in on-policy rein- forcement learning? large-scale empirical study. arXiv preprint arXiv:2006.0599) 2020.
Barreto, A., Dabney, W., Munos, R., Hunt, J. J., Schaul, T., Hasselt, H. P., and Silver, D. Successor features for transfer in reinforcement learning. In Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. wtt.:ttppss////oo/eeiiiee w urips..cc/ppper//////aass/////// 1525235354
Our work opens new avenues for enhancing representation learning in complex environments and lays out the assump- tions needed for its success. Future research could investi- gate how online Laplacian representation learning integrates with various learning paradigms, such linear value func- tion approximations or options learning. Additionally, important direction would be to explore its applicability in non-stationary settings, where the perceived transition dynamics change over time either due to changes in the environment or the interactions with other learning agents in the multi-agent scenario.
html.
Bengio, Y., Courville, A., and Vincent, P. Representation learning: A review and new perspectives. IEEE transac- tions pattern analysis and machine intelligence, 35(8): 1798-1828, 2013.
Chen, J., Aggarwal, V., and Lan, T. unified algorithm framework for unsupervised discovery of skills based on determinantal point process. Advances in Neural Infor- mation Processing Systems, 36. 2024.
Chicone, C. Ordinary differential equations with applica- tions. Springer, 2006.

---

Online Laplacian-Bel Haplacian-Based Representation Learning in Reinforcement Learning
Cho, G. E. and Meyer, C. D. Markov chain sensitivity measured by mean first passage times. Linear Algebra and its Applications, 3 316(1-3):21-2) 2000.
Learning, pp. 17198-17217. PMLR, July 2023, URL
pttps::/proceedinng .ew.ediinns..... wwigg.mlr.... wtt.smml...ree//22222. Hissarov2a..htm
Cho, G. E. and Meyer, C. D. Comparison of perturbation bounds for the stationary distribution of Markov chain. Linear Algebra and its Applications. 2001.
Koren, Drawing graphs by eigenvectors: theory and practice. Computers & Mathematics with Applications, 49(11-12)11867-18888 2005.
Kulkarni, T. D., Saeedi, A., Gautam, S., and Gershman, S. J.
Dayan, P. Improving generalization for temporal difference learning: The successor representation. Neural computa- tion, 5(4):6133624 1993.
Deep successor reinforcement learning. arXiv preprint 1rXiv:1606.02336 2016.
Laskin, M., Srinivas, A., and Abbeel, P. CURL: Contrastive unsupervised representations for reinforcement learning. Proceedings of the 37th International Conference on Machine Learning, pp. 5639-5650, PMLR, November 2020. URL htwp:: httpttppppppppeepeppeeettpppeeee ngg mlr. pres s/vl19 h/vl19/laskin2aa.herr htmll
Engstrom, L., Ilyas, A.. Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., and Madry, A. Implementation matters in deep policy gradients: A case study on PPO and TRPO. In International Conference on Learning Representations, 2020.
Even-Dar, E., Kakade, S. M., and Mansour, Y. Online Markov decision processes. Mathematics of Operations Research, 34(3):726-73,, 2009.
Machado, M. C., Bellemare, M. G., and Bowling, M. A Laplacian framework for option discovery in reinforce- ment learning. In International Conference on Machine PMLR, 2017a.
Learning, pp.
Farebrother, J., Greaves, J., Agarwal, R., Lan, C. L., Goroshin, R., Castro, P. S., and Bellemare, G. Proto- value networks: Scaling representation learning with aux- iliary tasks. arXiv preprint arXiv:2304.12560 2023.
Machado, M. C., Rosenbaum, C., Guo, X., Liu, M.,
Tesauro, G., and Campbell, M. Eigenoption discovery through the deep successor representation. arXiv preprint arXiv: /089, 2017b.
Fiedler, M. Algebraic connectivity graphs. Czechoslovak mathematical journal, 23(2):298-30) 305, 1973.
Machado, M. C., Barreto, A., Precup, D., and Bowling, M. Temporal abstraction reinforcement learning with the successor representation. Journal of Machine Learning Research, 24(80): 2023.
Funderlic, R. E. and Meyer Jr, C. Sensitivity of the sta- tionary distribution vector for an ergodic Markov chain. Linear Algebra and its Applications, 76:1-17, 1986.
Gimelfarb, M., Barreto, A., Sanner, S., and Lee, C.-G. Risk- aware transfer in reinforcement learning using successor features. In Advances in Neural Information Process- ing Systems, volume 34, pp. 17298 17310. Curran Asso- ciates, Inc., 2021. URL http://......tttpppp/eeeeeegeee .e urtjpp..c//apeerr000////ee//0000 (653c66266300006tssaa-----oo
Mahadevan, S. Proto-value functions: Developmental re- inforcement learning. In Proceedings of the 22nd inter- national conference on Machine learning ICML '05, pp. 553-560, Bonn, Germany, 2005. ACM Press. ISBN 978-1-59593-180-1. doi: 102151//12231111122221 URL htLpt/t::/ acm. wwtp://aaiotttocccooo/.o m7doid=1102351.110000
html.
Gomez, D., Bowling, M., and Machado, M. C. Proper Laplacian representation learning. arXiv preprint arXiv:2310.1083: 2023.
Mahadevan, S. Representation policy iteration. arXiv
preprint /207. 2012.
Mahadevan, S. and Maggioni, M. Proto-value functions: A Laplacian framework for learning representation and control in Markov decision processes. Journal of Machine Learning Research, 8(10), 2007.
Haviv, M. and Van der Heyden, L. Perturbation bounds for the stationary probabilities of finite Markov chain. Advances in Applied Probability, 16(4):804-818 1984.
Jinnai, Y., Park, J. W., Machado, M. C., and Konidaris, G. Exploration in reinforcement learning with deep cover- ing options. In International Conference on Learning Representations, 2019.
Melo, F. S., Meyn, S. P., and Ribeiro, M. I. An analysis of reinforcement learning with function approximation. Proceedings of the 25th international conference on Machine learning, pp. 664-671, 2008
Klissarov, M. and Machado, M. C. Deep Laplacian- based options for temporally-extender exploration. In Proceed- ings of the 40th International Conference on Machine
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidje- land, A. K., Ostrovski, G., et al. Human-level control
10

---

Online Laplacian-Based Representation Learning in Reinforcement Learning
through deep reinforcement learning. nature, 518(7540): 529-533, 2015.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06:3 2017.
Stooke, A., Lee, K., Abbeel, P., and Laskin, M. Decoupling representation learning from reinforcement learning. In Proceedings of the 38th International Conference on Ma- chine Learning, pp. 9870-9879. PMLR, July 2021. URL https: pettps//prron httpss::ppccceeieeeeeeee mlr, pwwssp tooke2la.hti hlm....
Sutton, R. S. Between MDPs and semi-MDPs: Learning, planning, and representing knowledge at multiple tempo- ral scales. 1998.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12. 1999.
Touati, A., Rapin, J., and Ollivier, Y. Does zero- shot reinforcement learning exist? arXiv preprint arXiv:2209. 14935, 2022.
Wang, K., Zhou, K., Zhang, Q., Shao, J., Hooi, B., and Feng. J. Towards better Laplacian representation in rein- forcement learning with generalized graph drawing. In Proceedings of the 38th International Conference on Ma- chine Learning, pp. 11003-11012. PMLR, July 2021. URL www.hhtpp...c.........tt http::tttt://pteeeee http:://pocceedeeee wgs. ml pat.rrpress//ee /vrv 39 39/wang2lae html.
Wu, Y., Tucker, G., and Nachum, O. The Laplacian in RL.: Learning representations with efficient approximations. arXiv preprint arXiv: 1810.0458, 2018
Xu, X., Huang, Z., Graves, D., and Pedrycz, W. A clustering- based graph Laplacian framework for value function ap- proximation in reinforcement learning. IEEE Transac- tions on Cybernetics, 44(12):2613-2625, December 2014. ISSN 1168-2275. doi: 10. 10.109//CCYB.221.23111177
Yuan, H. and Lu, Robust task representations for offline meta-reinnorreement learning via contrastive learning. In Proceedings of the 39th International Conference on Ma-
chine Learning, pp. 25747-25759. PMLR, June 2022. URL httpa/////.oceeeengg.....o ml press/vi 62/yuan22a. html.

---

Online Laplacian-Base Based Representation Learning in Reinforcement Learning
A. Proofs
A.1. Proof of Lemma 4.3
Proof. For an equilibrium point
(+)()
22 2 + 26
(ui Uz) uinnt + 26 ((u,, uidres 1)
2 0,
and since Pmin > 0, we can divide each element of the vectors on both sides by p(s) and we get,
( (2) = (1)(1) + 26
[ui uz) - 26 ((us, u0HO0 - 1) us = O,
j=1
We proceed by induction. For the base case with 1, we have
000
(u)())) 20 1
(tt) (1) fft + 26 (uu u1 ) -1) (1)) =0
Hence, either ui(h)
e (1) for some permutation : S + s and -2x
(t)
2b (nu) (u )200 -1) (i.e.
(t)
( ( =1
a
or i (1) = O.
200
Suppose now that either uj becomes
(1)
(1) oll) and (c)))) o0))o =
(0)
- or uj (()
0 for all j < then the gradient
Pu: [ (x=10))=11 (1)
22
x(1)
2b (11 ((1)) (000 11) (1)
,
2b
(u
(1) (0)
o0) 10
==1
Since the eigenvectors form basis, let u:
(t)
Σ
k=
19
Cu (1)
a(k)-
The gradient then becomes
Iuy (u (t))
2x((1) (kk)
+ (1u un ((0) )xO 1)) cize (1) ((R)
(13)
i-1
+ 26
(u, (1) (t) (1)
(0) 2000000 = 0.
Since the eigenvectors form a basis, all coefficients must be zero. For j < i and u² (1) * 0, we have:
(2x00) + 2b (uu. (1)) u. Hen - 1)) cis + 26(u, (t) (t)
(1))
( )ec =0
(14)
Now note that
Cj (u: (1) (t)
(e (1)
o( @ 2
Equation 14 then becomes
(1) (t)
2 + 2b
(1u , u )200 - 1)
+(t) x(1)
+ 2b
(u,
x()
(e)))) )
12

---

Online Laplacian-Base Based Representation Learning in Reinforcement Learning
Reordering the terms, we have:
2A 2 + 26 (14) ((1) x(t)
, 24 120 1+ (000) (66))(0)))))))))))))))))))))))
(2)
)
(uq -00))2100 0.
(4)
(e o))) 1 22)
Substituting (e (0()) ((0)) =1
(1)
we have:
b
2b(u,
=00 (10)
(u; , ( 0,
(G)) (())) 22)
(0)
26(n, ,r," [x(11) = 0, but the second condition is only true if (2)
which implies that either (u, (066) 2200 Caj = 0 or
(e
00)) x(1)
(1) = which implies that (u," 10) (t) / is always zero. For l 2 i in (13) or "s (()
";
(1) (t) ((k)
+ 26 (wu, (t) ; u, (0) (Hc - 1)) Cit: = 0
which implies that either Cak- = 0 or (u, (1) (t)
Note that and Cij can both be simultaneously (a) = A a()) i.e, " =(() is linear combination of eigenvectors for the same eigenvalue. Thus, we conclude
"
700
b
non-zero only if (8)
(00
(() (t) and (e
or u (+) 0. For non-zero, u, (+) it required that (1) [5)
that either u4 a())
A.2. Proof of Theorem 4.4
Proof. Let
12 (u)
92
(15)
Jd
where / is defined in (9).
We start by computing the Jacobian of (0) while applying the stop gradient operator. The matrix J = ()) is defined
such that each row of the matrix corresponds to the gradient of an entry of g()), We choose to apply the stop gradient operator when computing the Jacobian as optimizing the loss functions with the stop gradient operator analogous solving for u 's sequentially while fixing ú, where sequential losses would not include cross gradient term between and uj-
as shown by Gomez et al. (2023). Analyzing the stability of those
To determine the stability of the equilibrium points, we analyze eigenvalues of the Jacobian evaluated at them (Chicone, (t)
2006). Let m, II a. (,:(00000 and Pding diagonal matrix where Paing (s, (s) then
(1) (1)) = (V (2) (u TT
2L (1)
① (t) ② 1) + 2b (u, (6) (2)
u. 1200 (2)))000
1
Paiag
(t)
iif ofi=}
(16)
26 2(u (t) o (()) 2 (u! o () +
(ux o
(()) 2 (u (0)
p0)))
otherwise
Substituting the equilibrium points with the form derived in Lemma 4.3, i. u,
(t)
e
201 mi, (u(") (())))cc
(0)
13

---

Online Laplacian-Base Based Representation Learning in Reinforcement Learning
(1 1-- 5
my and (u) "jj ) - 0 for j j we get,
(1)
(0) (1) (V (Va.oel (u: TT
2L 2 (p
1) 21 (t) (t)
o11) P m; + 25pang (9)
(mp 1)+ ,if = j
ple)
4b(c
C p mm;+
0()
(17)
26
((k)
② (0)
@ ((() 2 p(()) m+
k=1
otherwise
Note that ((0 is a block diagonal matrix and its eigenvalues are the union of the diagonal blocks. We proceed to analyze the conditions for the block matrices to be positive definite, i. when (uz, is (w)))))))) is greater than zero
Vu, E {v E RiSI : v * 0}. Since the Laplacian operator is self-adjoint, the eigenvectors form basis for Rls), we
(t) in (ur, 1 (a)())))))))))))))))))))))))(() we get
can represent each U2 as a linear combination of eigenvectors. Let U, Ek=1 Gue ((k) | 1= Gae ((k) J (1) Σ C
((k)
(0 We first compute J is (n)(0)
Σ k= ((R) by replacing (=(()((0)()) with (17), we get
(1r10)
(2)
((k)
[s|
(24 n(c) o (t (t)
1) 210 (t) m, + 26p (m= - 1))
Σ
Giee o(A) +
(18)
k=1
S
4b(22) 2 ))) @ (e)))) 2 pp m;
)m; + 2b Σ
(oo) 2 ) 2 (e (Ca(s)
3 p )m)
cake (()
((k
j=1
Note that
(le!)) 2 p() 2 (ca()) 2 pp()))) (1)
ca(k)
= 0 -K #
and
(ee @ ( 2 p)))) elt)
((1) -e (1)
E())) 2000 (e()) ppl))
1
-11-
a(1)
(e))) O p())
Also note that 2L (t) pic 3 (pl0 @ 1) is matrix with (24/0) o (ol0 8 1)) (8, = L(s, 8') (1))))))))))))))))))))))))) (s')) and therefore for
any x E Rls)
(2 00s o (plt) 3 1)) 2(Lx) o ()
(19)
Substituting in (18) we get,
[s|
J (u (()
C
(t)
o(k) =
k=1
[8|
2 (100
- (1) m) + +2bbmi - 11) Gi co( 90
o(j)
(20)
+ 4bcule (()) 3 p((0) )m, - 40 (1)
((1) (e())) c p((0)
Σ
2bc,, o(5) 2 )m)))mm Σ 20 (1)
o6) (c() (6()) 2 pm))
1=1
14

---

Online Laplacian- Representation Learning in Reinforcement Learning
Now we reduced _ (1)) Σx Cre (k) to a linear combination (eo(1) @ p (t) (2))) 2 p000
(())) 2 pl1) with some
coefficients (a1, a2: a(s)). Since (Cy) as C o(k) @ p(o)) = axcucy (e (o1)) o(1))e00 and (e (00))) (01)) 1 = 0 for j A & we have
(1)
[s|
|5
Gase
( (A)) (u (1)
Cuee o(k)
Σ
uu ta le (0) (k) o(k))
(21)
H20 > 0 and ch 2 O, ag must be positive Ae for J (u+(t)) be positive definite. We group the conditions from (20) that required to be positive below
Since (a)) (tt)
2b(m; + m, - 1) - (2
o(1) m, + 2() (1- -m,) Vフșズ<iso
(2) o(1)
6bmn; + +21 62 m, 26
VI viiidd VI visijssss (S).
(22)
2(1 (1) m()) + 2b (m; - 1)
If any ui = 0, then the third condition becomes 2 2b which is always negative under the selection of hyperparame- ters discussed in Lemma 4.3, hence it is unstable. For equilibrium points where all u, (() conditions becomes
are non-zero, i.e m, 1V i, the
2h 21(0)
AI Mijsisd
9(0)
4b 41
sisid
(23)
(())
2( - -1())
Migi<j
The third condition indicates that 2()
0()) ((())) has to be positive which is only true for the identity permutation and if the maximum eigenvalue multiplicity of the Laplacian is The second and first conditions imply that b- X must be
positive which is true when bi > (1)) i |S| which is already a requirement of Lemma 4.3.
A.3. Proof of Proposition 4.5
Proof. To show that the gradient function gd)) is Lipschitz continuous, proceed to show that the spectral norm of the Jacobian is bounded Yu E C(O. Notice that the Jacobian defined in (16) is block diagonal matrix, hence its singular values are the union of the singular values of the block matrices J (u), and [w))l = max; |J (f))) By the triangle inequality we have,
09 (w)l S |26 o (o 1/|l + 26 ((u 1
, u; /300 - 1)
(0)
(e)
||
Pding
(24)
|ab(uL 19 @ ()) @ (u (4) (())
+ 2h
(1f
(1)
p(t) & (uk (u o p
We start by bounding the first term, by (19) we know that for any vector x E R|S (2L o (p(0) @ 1)) x ==((a))) 3 (0)
For any x E R| with ||=||| = 1.
(11g olo (6l0) & 11) x
(Lx)) 2 pb) V ((Tx) @ pl0) (Ix) @ p(0)
Σ (s)) V SES
[((L)(s)))
SEB
((Lx), (Lx) mio || & |[ | S |1
15

---

Online Laplacian-Bar Based Representation Learning in Reinforcement Learning
Therefore,
(24 pie) o (p @ 1))
2 2,
(25)
where (i) follows from ||00 - (Wu et al., 2018).
For the second term, since | |l < 1 and (u, u. )00
(t)
2 we have
Pmin
2b (uf) uj (1) HH0 - 1) Pdine - 2b (u{") u J2co Pding
+ 26
(2) Pdiag
+ 2b.
(26)
Piniin
For the remaining terms, note that for any x E IS with ||a:|| 1,
(1(u.) O ) 2 (u)) o pl)) x
(u, (8) 4o)
o p()) >1
| //lu///22002c
Ilzeco: 12,0 p
(27)
S |
|
1
1|u
12
2
Pmin
where (i) follows from u." being an element of the constraint set C(t)
Combining equations 25, 26, and 27 in (24), we get
12 + 4d
| (u)l sa= =a=2-- 2+ 2+
b.
Pmin
As the spectral norm of each block matrix J (u) is bounded by a Vu E c(t), the spectral norm of (v) is bounded by and the gradient g(*) is Lipschitz continuous with the Lipschitz constant a Vu E c(t).
A.4. Proof of Lemma 4.6
Proof for Lemma 4.6 (a)
Proof. We denote A(i,:) as the i-th row of the matrix A.
p(++1) p(t)
p((+1) -s.:))()())))
max
#ES
(n (1t+) (als) (a(os)))((
.ES
aEA
n =(++)( - (als) [| (s :l
max #ES
acA
(((+)) ( (als)) -0)
where (i) is by the triangle inequality, and (ii) from the fact that [[ :)1
Proof for Lemma 4.6 (c)
Proof. First note that the elements of the matrix (p(t) @ 1) O (t) ples are defined as
1. (1) (t)t) 1) e 1.000 (s, = (s) 1=) (s) (8, (0000))))))))))))))))))))))))))
= -s) (s. (t) 1
Hence, by applying the triangle inequality, we have
16

---

Online Laplacian-Bar Baaiia Representation Learning in Reinforcement Learning
(pl(tt) & 1) @ 1ett - -pp") @ 1) 1
|
(1)
- (plit1) 60 whtn + (pl)) @1) Doww
Pding
(t)
+ [((((tt)
W
(
Pding
- 8/ + (1ttt1) 2 o w
pittt) 10
W pl
1
s 660 + 2
20 1) 2 p((-1) - (p()
p())
1
(1olttt) e0 1) p((+)) - (0 s0 1) 1) p(o)
+ 2
And since ||AT|| || = ||A||| we have
|((00-1) @ 01)0 b - -po") @ 1) o _
(28)
s 566² + |(0ttt) 1) o p(++1) - (p e p())
Now we proceed to bound the second term, adding and subtracting (p(t+l) & 1) O p()) and applying the triangle inequality we have
(1blit1) & 1) o p((+2) - (0 & 1) @ plol
$1(0ttt)) s0 1) の (p(++)) - (p(++1) |coo + (( s0 1) - -00) s 1)) R pro
max #ES
(s) (pl)t) (s.)
+ V
max
(p) - ((o(3)) pon) :)
SES
S Visl p (+1)
p(ctt) - pmd) (s.:)
max 6ES
+ visi
(+1) 000|
max SES
VIS)((50) 6000 + 6
where (i) stems from the identity || S A for the n x n matrix A and (ii follows from ||
$ 1,
(s.))s 11 1, and Lemma 4.6(a).
Proof for Lemma 4.6 (d)
Proof. Recall that the loss function is given by:
j-1
(w) = Σ (uz, (0 u4) HOO +6 +b
(luy, [ux]]] munl) 2 b Σ (lui, unno - 1)²
(29)
We are interested in finding bound for the difference:
(u) (w) (1)
(30)
The first term in the loss function is:
Σ
(ua [(0 10ui)
(31)
2m
17

---

Online Laplacian-Baan Bascd Representation Learning in Reinforcement Learning
Substituting the inner product and applying the triangle inequality, have the following:
uus L [1++1)
21) Σ (us, L ((00))) 700t)) S
(32)
Σ
(u. 2 plt+1)" )L pletss (ui) - (u, o plt0) )L
ples (u:) ((s)
The above expression can be re- re-written as follows:
Σ Ui (loltt1) 2 1 1 (ol0) @ 31) o (8) mu
(33)
From Lemma 4.6(c),
(((+t)) @ 1) 2 ((t))) - -pp(1) @ 11)0 ② (()
S <0/ Thus, we have:
Σ
u T (plltl) & 1) ((tt)) - ( 2 1) o L (10
us)
S (1)
[u: ||
(34)
The difference in the regularization terms is:
(uug [u ((uj, [umI} +
k=1
(35)
b d ((u5 - 1)2 (luj, (luj, us)reto - 1)²)
2 j=1
Using the rule - = (x + v) (x y) and applying the triangle inequality, we can rewrite the above expression as follows:
1-1
Kuz, [uxl) + (uy, [ue]lmeo Kuy - (ug. |us +
1=1
(uy Un) H + (u,, 20) 211((1;,,))2(004) - (ugs (5)
2
j=1
(36)
b
Kuzs [ux]) (un (ug, (ecel K(ugs [un])aarH) - (mg, [
b
Kugi MyDaa + (ug, uoo [((z,, uz) (ug, (5)))))))))))
2
Note that
Kuy, [un])aet + (ug, [uI] S 2||u,|| (1|,,11-1[[4)) -||[=]]]|
(37)
and that
Kuj, [uelrac (uys (uul))ee0
Σ (s)) (s))
(38)
EES
s | [[x]]]] (1(()+1) - 11 - [|, ((0)
18

---

Online Laplacian-Bascl Representation Learning in Reinforcement Learning
where 8/ defined in Lemma 4.6(b).
Combining the bounds for both the first and second parts, the total bound on (() (w) is:
( S 5 Juel 2 + b [lll,|/1[[uu]1133]
(39)
j=1
We have (u)++ - (1)( S 062 where (/ is given by
N 1
21|u,|1 |1 11 (12000))
(40)
We know that ||uz||2 < 2/ Pmin Substituting this, we have
2d0 f.
8bc Piniin
(41)
Pman
From Lemma 4.6(b) and Lemma 4.6(c), we have 00 S C10% and 6% I C20lh for some constants C1 C2. Thus, we have [c(++)(x) (u) (u)) s g(6) (C1 + O2) This implies that the drift in the loss function decreases with the decrease in the drift between the policies N. and πt+1-
Note:
A.5. Proof of Theorem 4.7
Proof. Recall that the update rule for projected gradient descent in (10) is given by:
(++1)
(1)
n (n("),
"1
We need to prove that the gradient norm ([g (uy)l asymptotically approaches zero co, which would ensure the convergence critical point. In order to prove this, will establish that the sum of the squared gradients remains finite over time, despite the loss function being time-varying.
Recall the following assumptions:
The gradient of the time vime-iarying loss function (u)) is Lipschitz continuous with constant 0 for all t, that is,
(u1) V.g (t)2 (w2) S al|ur u2 ll. Vui, u2.
From Lemma 4.6, we have the change in the loss function from time to time + 1 is bounded by constant &g, i.e.,
[[ - 100) (x)ll S d0)
Vn.
Additionally, it is easy to see that the loss function ((*) (u) is bounded from below by constant L', i.e..
( (( (1) 2 L" Vu,l.
The descent lemma for loss function with Lipschitz continuuus gradients and learning rate is given by:
n? 2 all (u(t))11
(((+1) < c(++))()()) ( +
This can be rewritten as:
((++)) (u((l))))))))) (()) - (u())) (1
77
a (1())) 6()
2
19

---

Online Laplacian-Bas Based Representation Learning in Reinforcement Learning
where 62 represents the drift that accounts for the time-variation in the loss function between time /. and / + Rearranging this inequality, we obtain:
n " (u())) + +02 (((tt)) S L'0 (1 (1- 2 (1=²²
To ensure that the loss function decreases at each time step, except for the small drift dc, we require that:
2 a O.
This gives the condition on the learning rate:
11 < - α
Thus, the learning rate must satisfy 77 S 2 At each step, we can bound the change in the loss function as follows:
(u(()) (((+2))
n72 a
(100) -560
7
2
Summing this inequality over / = 1,2,..., T, we get:
Σ -C(t (((t)()))+)))
T
2 Σ (1~
T
n² r²a)
2 a) (x(0)]] 0622
-
The left-hand side of this inequality is a telescoping sum, so simplifies to:
(wd ((T+))
(1
1/2 a a)
|6 (u))) 5%6
Rearranging, we get:
T Σ (w0)))) (w()) ((T+))
Σ 8(1)
1 -/2 a
1 2
Since the loss function (1) is bounded from below by L" we have:
T
( (1)
L- Σ
(u0))2 566
11
2
t=1
We can further simplify this to:
(100))
(()(
L
Σi= 8(0
(42)
1) 5
2
Dividing both sides by T, we get
Unf.oonfooomLL...... (u] 5 (1
L*
Σ1 8
(0)
+
(43)
T
11
aa)
up
T
n2
Setting 17 . we have
T
E 1...uooommm22......
< T
2a
(1)
- L +
Σ (1)
3
(44)
t=l
20

---

Online Laplacian-Baan Bascd Representation Learning in Reinforcement Learning
From Assumption 4.2, we have that the asymptotic sum of the squared gradients lim
remains finite, i.c.,
T
lim T-+00
(u())) < cc. Therefore, we have:
lim 2-000
This shows that the gradients asymptotically approach zero over time, proving that the projected gradient descent algorithm applied to the time-varying loss function converges asymptotically to critical point.
B. Additional Experimental Details
We provide hyper-parameters for the Asymmetric Graph Drawing Objective (AGDO), Proximal Policy Optimization (PPO), and Deep-Q Network (DQN) in Table 1.
Table 1: prrpee-prrmeters for AGDO, PPO, and DQN.
Hyper-Paramene
AGDO
PPO
DQN
11
Replay Max Episodes
20
Updates per Episodic Step
Total Training Steps
200,000
Maximum Episode Length
10,000
Learning Rate
0.001
3 x 10 Adam
3 x 10 Adam
Optimizer
Adam
Barrier Coefficient
5
Encoder Network Hidden Dimensions
[256, 256, 256]
Batch Size
256
256
256
Replay Buffer Size
500 steps
50,000 steps
Update Every
500 steps
step
Training Batches per Update
10
1
Actor and Critic Hidden Dimensions
[64, 64]
Q-Network Hidden Dimensions
[64, 64]
Discount Factor
0.99
0.99
Entropy Coefficient
0.01
Initial Clip Ratio
0.2
Final Clip Ratio
0.01
Initial Epsilon
Final Epsilon
0.1
Finally, we present the rewards obtained by the learning agents described in Section 5, as illustrated in Figure Figure 6a shows the policies trained using the online version of AGDO across four different environments. In environments with larger state spaces, the total rewards are comparatively lower.
Figure 5a demonstrates that larger clipping improves the learning representation. However, as discussed in Section 5, this improvement comes at the cost of reduced policy quality and can seen Figure 6b.
Figures 6c and 6d depict effects of tuning parameters that influence only the encoder training. As result, the quality of the policies remains consistent across these experiments. In Figure 6c, the number of steps per policy update determines how frequently the encoder is updated. In Figure 6d, the size of the replay buffer is varied only for encoder training, while it remains fixed during policy training.
21

---

Online Laplacian-Bel Based Representation Learning in Reinforcement Learning
Rndilusmm
200
190 D.01-2.11
70
Grldfoomm
7P0 0.2-0.01
GrddMaae
60
150
Tital Rewant
Tinta Rewont
40
10
0
0.5
Enrtromment
x10
Enrironmenn
x3et
(a) Rewards for agents in Figure
(b) Rewards for agents in Figure 5a
Stepan1 Stops-5
Tglendeum1
Eylsodei-20
Stupo-10 10
60
Eylsodes=00
60
S1xps-220
Episoda-400 -400
Total Beaant
Total Rewenl
-30
30
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Stepa
Stapa
(c) Rewards for agents in Figure 5b
(d) Rewards for agents in Figure Sc
Figure 6: Average reward obtained by agents trained in section 5.
22


Reviews:
[{"review_id": "yolUC37NZG", "reviewer": "Reviewer_H35G", "summary": "The authors propose a theoretical analysis of an algorithm for online representation learning based on Laplacian eigenvectors. Current methods tend to learn representations based on a uniform/exploratory dataset, while the authors argue that representations evolve with policy changes and that more efficient learning can be achieved by considering this. Their algorithm is a simple modification of an established algorithm called ALLO. They prove that it is possible to learn representations efficiently, provided that policies do not change too rapidly (under bounded policy drift).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to give a thorough review. We address their questions and concerns below. Due to space constraints, we have shortened the quotes from the review. We also appreciate the reviewer’s suggestions in the \"Other Comments or Suggestions\" section and will address typos and clarifications in the final version or during the discussion phase if the reviewer provides a rebuttal comment.\n\n**Addressing the impact of learning the Laplacian representation online**\n> The fact that you ... imply much about learning a good policy, right?\n\nIndeed, this is a valuable insight. The accuracy of the learned representation does not necessarily imply a good policy.\n\n> How does the error .. converges to?\n\nAn accurate MDP representation improves sample efficiency and average returns, as shown in options learning (Chen et al., 2024), reward shaping (Wu et al., 2018), and linear function approximators for actor-critic methods (Mahadevan & Maggioni, 2007). While Laplacian representation learning typically relies on a fixed uniform policy, we argue that online learning can be more effective in scenarios with concentrated initial distributions. Additionally, our online learning method can be easily extended to non-stationary environments with a bounded drift. Finally, our method avoids extra pre-training samples by leveraging those already collected for policy training.\n\nRegarding the stationary point of the policy, depending on the type of reinforcement learning algorithm and the way it uses the representation, the stationary point of the algorithm could differ. For example, in an option learning method, it could correspond to multiple options with high coverage. In a reward-shaping goal-based environment, the stationary point could be a policy that reaches the goal. In our work, we assume that the policy and representation are learned in parallel and that the policy learning algorithm converges to some fixed point. The policy does not necessarily use the learned Laplacian features as inputs, instead the Laplacian representation can influence learning in other ways such as reward shaping or exploration rewards used in options learning.\n\n> In Section 2, you mention that previous ... learning?\n\nWe appreciate the reviewer raising this important point. We have not specifically tested the application of online representation learning for options learning. However, Klissarov and Machado’s work demonstrates that when the Laplacian representation is used solely for learning an exploration reward in an options learning framework and is used exclusively for exploration, both the online and fixed representations yield similar performance. While our current focus has not included this specific comparison, we plan in future work to explore broader applications of the learned representation, including value function approximation, reward shaping, and option learning frameworks that address both exploration and diversity. Additionally, we aim to investigate frameworks where learned options are actively utilized during the execution phase.\n\n**Contribution and Experimental Section**\n\nWe would like to confirm that to the best of our knowledge, this is the first work that addresses online Laplacian-based representation in reinforcement learning with theoretical guarantees. Our work provides the first analysis of the convergence of an online learning algorithm to the d-smallest eigenvectors of the Laplacian while updating the policy. Moreover, for a fixed policy, we provide an analysis for the convergence of AGDO to the d-smallest eigenvectors of the Laplacian which uses slightly different steps than the work by Gomez et al. However, we do not claim to be the first in online representation learning overall, as other methods, like successor features (discussed in Section 2), also learn policy and representation simultaneously.\n\nWe fully agree with the reviewer that further experiments showcasing the value of our framework in RL algorithms would strengthen the importance of our contributions. The contributions of the current work are more of a theoretical nature, laying the theoretical foundation for provable online Laplacian representation learning which is accompanied by simulations that support the accuracy of the learned representation. Building upon the developed theory, we will consider applications of the learned representation in options learning in future work.\n\n**Comparing AGDO and ALLO**\n\nSince AGDO is a simplified version of ALLO as it does not require an extra update step for the dual parameters, we empirically verify our theoretical analysis that AGDO, similar to ALLO, has the d-smallest eigenvectors as the only stable equilibrium. The results verify our claims. The reason they appear identical could stem from the fact that AGDO can be viewed as a regularized version of ALLO with a closed-form solution to the dual parameters as we discuss in section 4.1.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "I wish the experimental section were more extensive. The whole premise of the paper is that learning representations online provides an advantage over learning a fixed representation using a uniform policy. However, I do not see clear evidence of this in the experimental section.", "theoretical_claims": "No, I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "No, I have not.", "relation_to_broader_scientific_literature": "I believe the authors did a good job of providing an extensive literature review in Section 2, presenting a long line of work on learning Laplacian representations alongside a more recent perspective on representation learning using neural networks.", "essential_references_not_discussed": "It would be helpful if the authors could confirm whether this is indeed the first paper to provide guarantees for online representation learning, as this does not seem very likely to me.", "other_strengths_and_weaknesses": "I believe the question the authors aim to address is both important and challenging. The proposed method appears reasonable and applicable to realistic scenarios. The theoretical analysis is interesting, as it highlights the importance of bounded policy drift for efficient representation learning.\n\nOn the weaker side, I find the experimental section rather unconvincing. Additionally, I am unsure about the novelty of the methodological contribution in this paper.", "other_comments_or_suggestions": "- I am not sure what current overall policy in line 078 left means.\n- DCEO acronym in line 118 left is not explained\n- line 167 left, should be \"second to the smallest eigenvalue\"?\n- what is $\\Gamma$ in line 257 left?\n- Eq (9) should the last term be \"2b...\" or just \"b...\"?\n- Eq (10) should be $G_{u_i}^{(t)}(u^{(t)})$, then in line 280 again the same thing, and inside of the definition first $u_i$ should be $u_i^{(t)}$ I believe.\n- I am not sure that $L^{(t+1)}_{\\rho^{(t+1)}}$ in (c) in Lemma 4.6 has been defined previously. Also missing brackets for $t+1$ and $t$ superscripts in (d).\n- In Algorithm 1, line 5: should it be using $\\mathcal{A}$ and $u^{t+1}$?\n- Has $G^{(t)}$ in Theorem 4.7 been defined somewhere, since you used $G^{(t)}_{u_i}$ before?\n- line 372 right, last ALLO should be AGDO probably.\n- line 407 left, \":\" instead of \";\"", "questions_for_authors": "1. The fact that you can effectively learn representations of current policies does not necessarily imply much about learning a good policy, right? How does the error in your representation learning algorithm influence the policy update step? In other words, do you have any insight into the stationary point your algorithm converges to?\n\n2. Could you please comment on the purpose of comparing AGDO and ALLO? Based on the experimental results, they appear nearly identical, and it is not clear to me why solving ALLO would be more difficult.\n\n3. In Section 2, you mention that previous work has shown the online version of representation learning performs comparably to a two-stage variant of the algorithm. Have you conducted similar experiments for your algorithm? If so, and if the results are similar, what are the benefits of online learning?", "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": "dF4K1fpBs2", "reviewer": "Reviewer_XDtX", "summary": "The paper is about representation learning in RL. It analyses an online algorithm designed to learn Laplacian representations of a Markov Decision Process (MDP). Given a fixed policy $\\pi$, generally the exploratory policy, the Laplacian operator is defined as $L = I - \\frac{P_{\\pi} + P_{\\pi}^{\\ast}}{2}$, where $P_{\\pi}$ is the transition matrix of the Markov chain on states induced by $\\pi$, and $P_{\\pi}^{\\ast}$ is an adjoint to $P_{\\pi}$ with respect to some underlying measure. The Laplacian representation then consists in computing the first eigenvectors of L, for instance to perfom linear value function approximation. To avoid direct computation of the eigenvectors of $L$, earlier works have proposed optimzation procedures based on minimizing Rayleigh quotients: $\\min_{u_i} \\sum_{i=1}^{d} u_i^{\\top} L u_i$ as the minimum would be the sum of the first $d$ eigenvalues $\\sum_{i=1}^{d} \\lambda_i$, achieved for the d first eigenvectors of $L$. The specificity of this paper is to consider a setting where the policy $\\pi$ is no longer fixed but evolves in time, and learning of the Laplacian representation needs to be performed in an online manner while the policy evolves. This is motivated by earlier works which show empirically that learning Laplacian representations during exploration could improve performance. This paper aims to bring a theoretical counterpart to this work. The authors propose  thus a new optimzation objective, AGDO,  to perform online computation of the Laplacian representation, and study its convergence properties. In a first theorem, they show that under gradient descent dynamics, with a good choice of the parameters, the only stable equilibrium points correspond to the true Laplacian eigenvectors. Secondly, they propose an online projected gradient descent (OPGD), which under a drift assumption on the policy process, is proved to converge towards this equilibrium. This theoretical work is completed with numerical experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thoughtful and considerate comments. Below we address their remark about related work.\n\n> I don't have a lot of suggestions for the authors. They mention however successor representations in the related work section, so I wondered if maybe their work and method could also be related with the work \"Does Zero-Shot Reinforcement Learning Exist?\" by Touati \\& al ? In the latter and the references therein, the authors propose a \"forward-backward\" representation of a RL problem which is based on a low-rank approximation of the successor measure. I think there could be a common point with the present paper in that learning their model requires updating the policies and the representation at the same time.\n\nWe appreciate the reviewer's suggestion; this paper is indeed relevant to our work. Touati et al. explore approximate zero-shot reinforcement learning, where an agent first learns environment features in a reward-free phase and then deploys a learned linear approximation of the reward function. Their study compares two approaches:\n\n- Successor Features Representation – Elementary features are learned offline, followed by successor feature learning.\n\n- Forward-Backward Representation – Both elementary and successor features are learned simultaneously.\n\nTheir results highlight that Laplacian-based representations outperform other feature choices. Furthermore, the dynamic approach of jointly learning elementary and successor features proves to be superior.\n\nThis work underscores the importance of high-quality representation learning, the effectiveness of Laplacian-based representations, and the benefits of jointly learning representations. We will incorporate this discussion into the successor feature paragraph in Section 2.", "claims_and_evidence": "I haven't given a thorough look at the proofs in the appendix, but this work appears as serious to me, the authors provide proofs for all their claims. It builds on prevous works about computing Laplacian eigenvectors through minimization objective and adapts them to the online setting.", "methods_and_evaluation_criteria": "The AGDO objective and optimization methods used in the paper build on a series of work on Laplacian representations intitiated with the paper of Koren 2005. In that regard I think the algorithm is well motivated. It could be considered a limitation however that the experiments limit to gridworld and maze environments.", "theoretical_claims": "Due to a lack of time I haven't checked completely the proofs of the theoretical claims.", "experimental_designs_or_analyses": "The content of the paper is mostly theoretical, and I have nothing to complain about when it comes to the experimental work.", "relation_to_broader_scientific_literature": "Laplacian representations have been a recurring theme in RL during the last 20 years. This paper is mostly concerned with the numerical aspects and algorithms that compute eigenvectors while avoiding matrix computations. The basic idea appeared in a work by Koren 2005 who proposed computing eigenvectors exploiting the fact they minimize Rayleigh quotients. Since then a series of work have improved on this approach, notably to address symmetry issues resulting in non-uniqueness of the solutions for the minimization objectives. The present paper draws inspiration from the most recent work in that aspect (Gomez \\& al. 2023), to adapt the idea to an online version of the problem. This is motivated by a paper of Klissarov \\& Machado 2023, which showed experimentally that improvements could be made by updating jointly the policy and the representation.", "essential_references_not_discussed": "In my opinion the paper already cites the most relevant references.", "other_strengths_and_weaknesses": "The paper provides both a theoretical and empirical study of the online learning of Laplacian representations. It is well presented and clear.", "other_comments_or_suggestions": "I don't have a lot of suggestions for the authors. They mention however successor representations in the related work section, so I wondered if maybe their work and method could also be related with the work \"Does Zero-Shot Reinforcement Learning Exist?\" by Touati \\& al ? In the latter and the references therein, the authors propose a \"forward-backward\" representation of a RL problem which is based on a low-rank approximation of the successor measure. I think there could be a common point with the present paper in that learning their model requires updating the policies and the representation at the same time.", "questions_for_authors": "I dont't have a big concern or question whose answer would heavily affect my opinion on the paper.", "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": "1SLI6py5NI", "reviewer": "Reviewer_2pDa", "summary": "The paper titled \"Online Laplacian-Based Representation Learning in Reinforcement Learning\" explores the integration of Laplacian-based representation learning within reinforcement learning (RL) frameworks. The authors address the challenge of learning Laplacian-based representations online and with theoretical guarantees along with policy learning. They propose an online optimization approach using the Asymmetric Graph Drawing Objective (AGDO) and demonstrate its convergence through online projected gradient descent.\nThe authors introduce AGDO, a simplified version of the Augmented Lagrangian Laplacian Objective (ALLO), and provide theoretical bounds for its convergence. The empirical analysis evaluates the accuracy of the proposed method in both fixed and online settings. Moreover, the experiments demonstrate that AGDO achieves performance comparable to ALLO. Finally, the authors analyze the impact of different components, such as bounded drift, number of update steps, and replay buffer size, on the accuracy of the learned representations.\n\nThe main contributions of the paper can be summarised as follows:\n - The authors introduce the Asymmetric Graph Drawing Objective (AGDO), a simplified version of ALLO that eliminates the need for dual variables.\n - They provide theoretical bounds for the convergence of AGDO under gradient descent dynamics.\n - The paper includes extensive simulation studies that empirically validate the convergence guarantees to the true Laplacian representation.\n- The authors provide insights into the compatibility of different reinforcement learning algorithms with online representation learning.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and addressed their questions and concerns below.\n> Bounded drift assumption\n\nRegarding the concern about drastic or erratic policy shifts in real-world RL scenarios, our theoretical analysis explicitly assumes bounded policy drift (Assumption 4.2). This is a desired feature of many RL algorithms in practice such as conservative policy iteration, PPO, and TRPO, which naturally limit such drastic shifts. Our convergence results hold under this assumption. Whether this assumption could be relaxed or modified for algorithms not promoting bounded drift would be an important and interesting future investigation. We acknowledge that handling larger or unpredictable policy changes would enhance practical robustness. Incorporating adaptive step-size methods or robust regularization techniques to explicitly avoid large policy deviations is a promising direction for future extensions of our framework.\n\n> Effect of number of update steps\n\nWe would like to clarify that we do not make theoretical claims in the paper for the effect of the number of update steps on the performance. However, we empirically study the effect on the number of update steps and hypothesize that the discrepancy in the expected behavior is due to the presence of noise, caused by sampling from the replay buffer. We discuss this in detail in Section 5 (lines 430-436) as follows: \"In Figure 4b, we analyze the effect of increasing the number of steps. We vary the number of update steps per sample between 1 and 20. While an increase in the number of steps is expected to enhance accuracy, our findings indicate that this is not observed. We hypothesize that this discrepancy is  due to the presence of noise, caused by sampling from the replay buffer.\"\n\n> Replay buffer size\n\nWe absolutely agree with the reviewer's insight. In fact, we highlight this in Section 5 (lines 401-411) as follows: \"In the online setting, the buffer would include steps from previous policies with different stationary and transition distributions which would introduce bias to our loss estimate. However, a small buffer size would also increase the variance of the estimate. This is confirmed by the results, as for a buffer that holds only one episode we see a worse performance than a buffer that holds 20 episodes. On the other hand, increasing the buffer size drastically also causes accuracy to drop as the samples used have a different distribution which can be seen for buffers with sizes 50 and 400\". Hence, a careful balance of the buffer size is important to balance the variance and bias in the loss estimates. \n\n> Limited real-world validation\n\nWe fully agree with the reviewer that further experiments showcasing the value of our framework in RL algorithms would strengthen the importance of our contributions. The contributions of the current work are more of a theoretical nature, laying the theoretical foundation for provable online Laplacian representation learning which is accompanied by simulations that support the accuracy of the learned representation. Building upon the developed theory, we will consider applications of the learned representation in options learning in future work.\n\n> Complexity of theoretical analysis\n\nThis work builds upon an existing line of work that uses rigorous mathematical methods that provide both a practical application through empirical intuitive evaluations in addition to theoretical guarantees. The major contributions of this work are more of a theoretical nature, and given the complexities of joint representation learning and reinforcement learning, unfortunately, the theoretical analysis and results are unavoidably involved. Overall, our work offers rigorous proofs for the involved reader and in addition empirical results along with practical discussions and evaluations to provide some intuition of our theoretical findings.", "claims_and_evidence": "The claims are generally supported by the evidence (with a few exceptions)\n\nWell-supported claims:\n\n1. Introduction of AGDO:\n - The paper introduces the Asymmetric Graph Drawing Objective (AGDO) as a simplified version of the augmented Lagrangian Laplacian objective (ALLO). This claim is supported by a detailed formulation of AGDO and its comparison with ALLO.\n2. Theoretical analysis:\n - The authors provide theoretical bounds for the convergence of AGDO under gradient descent dynamics. This claim is supported by rigorous mathematical proofs and assumptions laid out in the paper, particularly in sections 4.2 and 4.3.\n3. Empirical validation: \n - The paper includes extensive simulation studies that empirically validate the convergence guarantees to the true Laplacian representation. Figures 2 and 3 show the average cosine similarity between the true Laplacian representation and the learned representation using AGDO and ALLO, demonstrating comparable performance.\n4. Compatibility insights: \n - The authors provide insights into the compatibility of different reinforcement learning algorithms with online representation learning. This claim is supported by empirical analysis and ablation studies, as shown in Figure 4, which analyze the impact of bounded drift, number of update steps, and replay buffer size on the accuracy of the learned representation.\n\n\nQuestions on other claims:\n\n1. Bounded drift assumption:\n - The paper assumes that the drift in the policy caused by the policy learning algorithm is bounded. While this assumption is valid for many policy learning algorithms, the empirical evidence provided (Figure 4a) shows that the accuracy of the learned representation can vary significantly depending on the drift bound. The claim that bounded drift is necessary for learning an accurate representation is supported, but the variability in accuracy may suggest that further investigation is needed to fully understand the impact of different drift bounds.\n\n2. Effect of number of update steps: \n - The paper claims that increasing the number of update steps per sample collected should enhance accuracy. However, the empirical findings indicate that this is not always observed, possibly due to noise caused by sampling from the replay buffer. This discrepancy suggests that the claim may need further empirical validation and refinement.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria in the paper make sense for the problem and application at hand.", "theoretical_claims": "No", "experimental_designs_or_analyses": "Please, find below comments concerning the soundness and validity of the experimental designs and analyses presented in the paper as well as some issues\n\n1. Grid world environments: \n - The use of grid world environments for testing the proposed methods is appropriate. These environments provide a controlled setting to evaluate the accuracy and convergence of the learned representations. The design includes varying the complexity of the environments, which helps in assessing the robustness of the methods.\n2. Comparison with ALLO: \n - The experiments compare the performance of AGDO with ALLO in both fixed and online settings. This comparison is valid and provides a clear benchmark to evaluate the effectiveness of AGDO. The use of average cosine similarity as a metric is appropriate for measuring the alignment between the true and learned representations.\n3. Ablation studies\n - The ablation studies analyze the impact of bounded drift, number of update steps, and replay buffer size on the accuracy of the learned representation. These factors are directly relevant to the performance of the proposed methods, making the experimental design comprehensive and insightful.\n4. Theoretical analysis: \n - The paper provides a detailed theoretical analysis of the convergence of AGDO under gradient descent dynamics. The assumptions and mathematical proofs are clearly laid out, supporting the validity of the theoretical claims.\n5. Empirical validation: \n - The empirical results are presented with average cosine similarity metrics and confidence intervals, which provide a clear and statistically sound measure of performance. The results show that AGDO achieves performance comparable to ALLO, supporting the claim of its effectiveness.\n\n6. Bounded drift assumption - see Claims And Evidence\n7. Effect of number of update steps - see Claims And Evidence\n8. Replay buffer size: \n - The impact of replay buffer size on the accuracy of the learned representation shows that both very small and very large buffer sizes can negatively affect performance. This highlights the importance of carefully tuning the buffer size to balance variance and bias in the loss estimate.", "relation_to_broader_scientific_literature": "The key contributions of the paper are closely related to several prior findings, results, and ideas in the broader scientific literature.\n\nRelated findings/results/ideas:\n\n1. Proto-Value functions: \n - The concept of proto-value functions introduced by Mahadevan (2005) is foundational to Laplacian-based representation learning. Proto-value functions are eigenfunctions of the normalized Laplacian of the graph generated by a random walk over the state space. This idea has influenced subsequent work on Laplacian representations, including the current paper's focus on eigenvectors of the Laplacian matrix.\n2. Graph drawing objective: \n - The graph drawing objective proposed by Koren (2005) has been a key method for approximating Laplacian representations in large state spaces. Wu et al. (2018) extended this method to continuous state spaces, demonstrating its applicability through stochastic optimization. The current paper builds on these ideas by introducing AGDO and validating its performance.\n3. Successor features: \n - The deep successor representation introduced by Kulkarni et al. (2016) decomposes the value function into a successor feature function and a reward predictor function. This approach has found applications in transfer learning and options discovery. The current paper's focus on Laplacian-based representation learning is related to these ideas, as both methods aim to improve RL algorithms' performance through better state representations.\n4. Contrastive learning: \n - Contrastive learning methods, such as those proposed by Laskin et al. (2020) and Stooke et al. (2021), aim to learn representations that distinguish between similar and dissimilar pairs of data points. These methods are closely related to Laplacian-based representation learning, as both approaches seek to capture the geometry of the underlying state space. The current paper's empirical validation of AGDO aligns with these prior findings.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths**\n\n1. Innovative approach:\n - The introduction of the Asymmetric Graph Drawing Objective (AGDO) as a simplified version of the augmented Lagrangian Laplacian objective (ALLO) is innovative. It addresses the complexity of dual variables, making the method more practical for online learning scenarios.\n2. Comprehensive empirical validation: \n - The extensive simulation studies in both fixed and online settings provide strong empirical evidence for the effectiveness of AGDO. The use of average cosine similarity as a metric is appropriate and provides clear insights into the performance of the learned representations.\n3. Compatibility insights: \n - The paper offers valuable insights into the compatibility of different reinforcement learning algorithms with online representation learning. This is particularly useful for practitioners looking to integrate AGDO with various RL frameworks.\n4. Ablation studies: \n - The ablation studies analyzing the impact of bounded drift, number of update steps, and replay buffer size are insightful. They help in understanding the factors that influence the accuracy and performance of the learned representations.\n\n\n**Weaknesses**\n\n1. Bounded drift assumption:\n - The paper assumes that the drift in the policy caused by the policy learning algorithm is bounded. While this assumption is valid for many policy learning algorithms, the empirical evidence provided (Figure 4a) shows that the accuracy of the learned representation can vary significantly depending on the drift bound. The claim that bounded drift is necessary for learning an accurate representation is supported, but the variability in accuracy may suggest that further investigation is needed to fully understand the impact of different drift bounds.\n\n2. Effect of number of update steps: \n - The paper claims that increasing the number of update steps per sample collected should enhance accuracy. However, the empirical findings indicate that this is not always observed, possibly due to noise caused by sampling from the replay buffer. This discrepancy suggests that the claim may need further empirical validation and refinement.\n\n\n3. Replay buffer size: \n - The impact of replay buffer size on the accuracy of the learned representation shows that both very small and very large buffer sizes can negatively affect performance. This highlights the importance of carefully tuning the buffer size to balance variance and bias in the loss estimate.\n\n5. Limited real-world validation: \n - The experiments are conducted in grid world environments, which, while useful for controlled testing, may not fully capture the complexities of real-world RL scenarios. Further validation in more complex and realistic environments would strengthen the findings.\n\n6. Complexity of theoretical analysis: \n - The theoretical analysis, while rigorous, is quite complex and may be challenging for readers without a strong mathematical background. Simplifying some of the explanations or providing more intuitive insights could make the paper more accessible.", "other_comments_or_suggestions": "See Other Strengths And Weaknesses", "questions_for_authors": "See Other Strengths And Weaknesses", "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": "5pWxnQ2QnT", "reviewer": "Reviewer_bt1X", "summary": "This paper studies how to learn a Laplacian-based state representation in an **online** manner for reinforcement learning, rather than fixing a policy and then extracting a representation from its induced Markov chain. The authors propose a modified “asymmetric graph drawing” objective (AGDO) that can be jointly optimized with the policy’s updates, ensuring that the representation automatically adapts to policy changes. They prove that under mild assumptions about how quickly the policy changes, online projected gradient descent on AGDO converges and recovers the true Laplacian embedding of the evolving Markov chain. Empirical experiments in grid-world environments validate these guarantees and show that AGDO-based online learning can match the quality of prior offline Laplacian objectives, with advantages when the policy is updated throughout training.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's efforts in reviewing our work and providing their detailed feedback. Below we address their questions and concerns.\n\n**Zero Eigenvectors**\n\nWe thank the reviewer for this insightful suggestion. Based on our analysis, we do not expect degenerate partial solutions to be stable. To further investigate this, we plan to conduct additional experiments by resetting one of the eigenvectors to near zero after a fixed number of training steps and observing how the representation evolves.\n\n**Bounded Drift**\n\nWe thank the reviewer for their valuable suggestion. In Section 5 of the paper, we present empirical results for scenarios where the policy update may undergo rapid changes. Specifically, we present experimental results for Deep Q-Network (DQN), where the policy improvement step (i.e., greedy selection of actions) does not guarantee bounded policy drift. In Figure 4.1 (a) in which we compare the effect of bounded drift on the accuracy of the learned representation, Vanilla policy gradient (VPG) which might have drastic changes, and PPO (0.2, 0.01) follow a similar trend during the first $10^5$ steps. However, as PPO policy starts to stabilize the gap in accuracy increases at the end. This demonstrates that the total drift in addition to the drift limit matters more towards the accuracy of the representation quality in the long run as discussed by our assumption. In addition, we also compare the effect of rapid changes in the DQN algorithms. Through empirical studies, we conclude that the bounded drift assumption is necessary for learning an accurate representation. Additionally, we would like to highlight that the bounded policy drift is a desired feature of many RL algorithms in practice such as conservative policy iteration, PPO, and TRPO, which naturally limit such drastic shifts.\n\n\n\n**Contribution**\n\nTo the best of our knowledge, this is the first work that addresses online Laplacian-based representation in reinforcement learning with theoretical guarantees. Our work provides the first analysis of the convergence of an online learning algorithm of the d-smallest eigenvectors of the Laplacian while updating the policy. Moreover, we provide an analysis for the convergence of AGDO (which is equivalent to ALLO with beta = 0) to the d-smallest eigenvectors of the Laplacian which uses slightly different steps than the work by Gomez et al(2023). Indeed, the work by Gomez et al.(2023) has been influential for our work, as it showed that optimizing the ALLO objective has the d-smallest eigenvectors as the only stable equilibrium for a fixed policy. We clarify the following in Section 4.2 of the paper: \"This result is similar to Lemma 2 derived by Gomez et al.(2023) with the norm of the vectors being different and the fact that the vectors can be zero\". However, we show in Theorem 4.4 that only the identity permutation with non-zero vectors corresponds to a stable equilibrium under a proper selection of hyperparameters. Additionally, our convergence analysis of the Laplacian representation in the online setting presents a novel perspective that, to our knowledge, has not been explored in prior work.\n\n\n\n**Extention to Large-scale Function Approximator and Continuous Control**\n\nWe fully agree with the review that further experiments showcasing the value of our framework in RL algorithms would strengthen the importance of our contributions. The contributions of the current work are more of a theoretical nature, laying the theoretical foundation for provable online Laplacian representation learning which is accompanied by simulations that support the accuracy of the learned representation. Building upon the developed theory, we will consider applications of the learned representation in options learning in future work.\n\nSince our approach is built on standard online SGD and representation learning frameworks, it can be easily integrated in larger function approximators, going beyond MLPs over low-dimensional inputs. For example, the empirical study by Klissarov and Machado (2023) utilizes a convolutional neural network to learn the Laplacian representation in an online manner and uses the representation to learn options with high coverage.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The central theorems establish that, under a bounded-drift assumption on the evolving policy, online projected gradient descent on the authors’ asymmetric graph-drawing objective converges (in an ergodic sense) to a critical point of the Laplacian representation. The paper’s proofs rely on two main ingredients:\n\n1. **Equilibrium Characterization:**  \n   They show that if you hold the policy (and thus the underlying operator) fixed, then gradient descent on the proposed objective converges to a set of stable equilibrium points that match the smallest Laplacian eigenvectors. The argument resembles that of prior Laplacian objectives such as ALLO, but with “asymmetric” terms (including a stop-gradient operator) to break rotational symmetries.  \n   - The lemma mapping equilibrium points to eigenvectors (possibly permuted) follows an inductive argument on the dimension of each learned vector.  \n   - They then use a Jacobian-based stability analysis to show only the identity permutation is stable, and only if the vectors are all non-zero – which corresponds to the true eigenvectors in the correct order.\n\n2. **Online Convergence:**  \n   They next show that with a policy that may change between steps but remains “close” from one update to the next (i.e. bounded drift), the difference in the objective from step to step is small enough to maintain progress. By combining a standard smoothness argument for gradient-based optimization with a drift analysis of the Markov chain, they give an ergodic bound on convergence to a stationary point.\n\nOn a closer look, the arguments generally follow a standard pattern in time-varying optimization:  \n- Proving each fixed-instance problem is well-behaved (smoothness, stable equilibria).  \n- Bounding the “error” introduced by drift in the environment’s operator.  \n- Applying a convergence result for online or dynamic projected gradient methods.\n\nSo far, the proofs appear internally consistent. Two subtle points might merit further scrutiny or clarification:\n\n1. **Zero or Degenerate Eigenvectors**:  \n   Their analysis for “stable” equilibria relies on each eigenvector being non-zero (otherwise you could have fewer than \\(d\\) total eigenvectors). Although they show that only the full set is stable, it might be worth confirming if degenerate (partial) solutions could become temporarily stable under certain conditions in practice.\n\n2. **Bounded-Drift Constant**:  \n   The drift assumption is crucial. The text references a sublinear bound on the cumulative changes to the policy. In practice, large updates might occur at times, especially before the policy converges. Whether the theorems still hold if the policy sometimes shifts drastically (but remains small in the long run) is an open question, though the paper’s arguments do rely on standard constraints from policy-gradient or trust-region methods.\n\nOverall, the proofs for both static and dynamic cases align with prior lines of analysis in Laplacian representation learning and dynamic gradient-based optimization. There are no obvious errors in how they apply known stability and perturbation lemmas, and the reasoning steps seem coherent with the stated assumptions.", "experimental_designs_or_analyses": "Yes, no issue", "relation_to_broader_scientific_literature": "This work extends the established line of **Laplacian-based representation learning**—often called proto-value functions or eigenoptions in reinforcement learning—from an offline, fixed-policy setting to a fully **online** one where the policy (and thus the Markov chain) evolves over training. Prior studies had shown how to approximate Laplacian eigenvectors efficiently or how to break the rotational symmetry in eigenvector solutions, but only for a single static operator. Recent empirical work (for instance, in learning options with deep Laplacian representations) explored updating the representation while the policy changed, but without providing rigorous convergence guarantees.  \n\nIn that sense, the paper (1) **proposes a variant** of previously known objectives (such as the “augmented Lagrangian Laplacian objective,” ALLO) that uses an “asymmetric” construction and (2) **proves** that projected gradient descent still converges in the presence of modest policy drift. It thus unifies two strands of the literature:  \n- The original demonstration that one can recover Laplacian eigenvectors through unconstrained objectives, plus symmetrical-breaking terms to ensure uniqueness.  \n- The desire in RL to keep updating representations as policies improve, preventing mismatch between the learned embedding and the actual transitions.  \n\nHence, the authors build upon standard results for **Laplacian-based embedding** (Koren’s graph-drawing objective, Wu et al.’s approach for approximating the operator under a fixed policy, and Wang et al. and Gomez et al. for clarifying uniqueness/stability) and carry these ideas forward into **time-varying, policy-dependent** scenarios—bridging a gap in the prior literature where theoretical guarantees were lacking for fully online adaptation.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "## Strength\n- The paper makes a clear, novel contribution by theoretically extending Laplacian-based representation learning to time-varying RL settings and confirming convergence under bounded policy drift. This is a welcome step in bridging purely offline methods and practical “end-to-end” RL pipelines that adapt representations as policies improve. The significance lies in demonstrating that Laplacian embeddings can remain valid in a continuously evolving MDP, which in turn may improve exploration and stability in practice.\n\n- One notable strength is the careful balance of theoretical rigor and empirical demonstration, where each assumption (especially the drift bound) is mapped back to commonly used techniques like trust-region updates. The authors also provide experiments confirming that performance benefits hold in multiple grid-world variants and that, indeed, the policy’s drift rate is a key factor. Such clarity on what matters for “online Laplacian learning” makes the result more interpretable and actionable.\n\n## Weakness\n- A potential weakness is that real-world RL scenarios could see more drastic or erratic policy shifts, at least early on, than the sublinear bound presumes. The paper does address this by suggesting smaller step sizes or stable policy updates, but more thorough discussion of how to handle genuinely large, unpredictable changes would strengthen the practical impact. Another small drawback is that the experiments revolve around relatively small navigation tasks; whether the same approach is straightforward to integrate in large-scale function approximators (beyond MLPs over low-dimensional input) or more complex continuous-control benchmarks remains open. Nonetheless, the clarity and step-by-step build-up of the main algorithm, plus the thorough theoretical arguments, make the paper a meaningful contribution in bridging offline eigenvector-based representations and real-time RL learning.\n\n- It remains doubt that how much the theoretical contribution of this work relies on the existing work of Gomez et al. (2023). The authors may need to explicitly mention the uniqueness of their theoretical contribution in the main paper.", "other_comments_or_suggestions": "please refer to weaknesses", "questions_for_authors": "- Q1: he theoretical guarantees assume bounded policy drift. Have you tested cases where the policy undergoes rapid, large updates (e.g., early in training when exploration is high)? Would the method still be stable, or do you observe degradation in representation accuracy?\n\n- Q2: Your experiments focus on grid-world settings with relatively simple representations. Have you explored how well this approach scales to high-dimensional, visual, or continuous-control environments? Would convolutional or attention-based architectures be needed to maintain stability in more complex tasks?", "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:

Meta-review: The reviews generally lean towards acceptance for providing valuable contributions to an well-studied area of representation learning for RL, with some weakness around the limitations of the experimental work. I tend to agree with both of these points, but also want to highlight a comment made by the author(s) that could be revisited.

In response to a reviewer question: “The fact that you can effectively learn representations of current policies does not necessarily imply much about learning a good policy, right?”

The author(s) indicate “The accuracy of the learned representation does not necessarily imply a good policy.”

There are results in approximate policy iteration (e.g. Error bounds for approximate policy iteration. Munos. 2003) and elsewhere that could be used to argue that (stated informally) having representations that accurately represent the value function for policies throughout policy improvement leads to improved bounds on the quality of the policy you converge to. So, while having effective representations for current policies does not *imply* a better policy, it could improve the upper bound on the eventual learned policy.
Decision: Accept (poster)